LeetCode 2684. 矩阵中移动的最大次数
原题链接
中等
作者:
我是java同学
,
2023-09-21 17:09:02
,
所有人可见
,
阅读 57
class Solution {
public:
int dx[3] = {-1, 0, 1}, dy[3] = {1, 1, 1};
int n, m;
vector<vector<int>> g, cnt;
int dfs(int x, int y) {
if (cnt[x][y] != -1) return cnt[x][y];
int res = 0;
for (int i = 0; i < 3; i ++ ) {
int a = x + dx[i], b = y + dy[i];
if (a >= 0 && a < n && b >= 0 && b < m && g[a][b] > g[x][y])
res = max(res, dfs(a, b) + 1);
}
cnt[x][y] = res;
return res;
}
int maxMoves(vector<vector<int>>& grid) {
g = grid;
n = g.size(), m = g[0].size();
int res = 0;
cnt = vector<vector<int>>(n, vector<int>(m, -1));
for (int i = 0; i < n; i ++ )
res = max(res, dfs(i, 0));
return res;
}
};