华为题：矩阵中的最长递增路径

对于每个单元格你可以往上、下、左、右四个方向移动。不能沿对角线移动也不能移动到矩阵边界外。输入描述第一行输入两个整数m和n表示矩阵的行数和列数。接下来输入m行每行n个整数。输出描述输出最长递增路径的长度。示例 1输入text3 3 9 9 4 6 6 8 2 1 1输出text4说明最长递增路径为1 - 2 - 6 - 9。C 解法cpp#include bits/stdc.h using namespace std; int m, n; vectorvectorint matrix, memo; int dirs[4][2] {{1,0},{-1,0},{0,1},{0,-1}}; int dfs(int x, int y) { if (memo[x][y] ! -1) return memo[x][y]; int best 1; for (auto d : dirs) { int nx x d[0]; int ny y d[1]; if (nx 0 nx m ny 0 ny n matrix[nx][ny] matrix[x][y]) { best max(best, 1 dfs(nx, ny)); } } return memo[x][y] best; } int main() { cin m n; matrix.assign(m, vectorint(n)); memo.assign(m, vectorint(n, -1)); for (int i 0; i m; i) { for (int j 0; j n; j) { cin matrix[i][j]; } } int ans 0; for (int i 0; i m; i) { for (int j 0; j n; j) { ans max(ans, dfs(i, j)); } } cout ans endl; return 0; }