看优秀摄影做品的网站,微信网站开发流程,可以免费打广告的平台,wordpress子网站1. 题意
矩阵中一个位置只能从左上一、左、左下一格子转移而来#xff0c;且当前值一定大于转移之前的值#xff1b;
求从第一列开始的最大转移步数。
矩阵中移动的最大次数
2. 题解
思路 由于状态只能从左向右转移#xff0c;所以同一个位置被搜索到后#xff0c;第一…1. 题意
矩阵中一个位置只能从左上一、左、左下一格子转移而来且当前值一定大于转移之前的值
求从第一列开始的最大转移步数。
矩阵中移动的最大次数
2. 题解
思路 由于状态只能从左向右转移所以同一个位置被搜索到后第一列其他位置再搜索到它的距离一定相等。题目求得是第一列转移到其他位置的最大次数我们需要把第一列置0,其他列置 MINVAL。使得只有从第一列转移的才能使得值为正数。
class Solution {
public:struct Dir {constexpr static int dir[][2] {{1,-1},{0,-1},{-1,-1}};};int maxMoves(vectorvectorint grid) {int w grid[0].size();int h grid.size();int MIN_VAL -2000;int ans 0;vectorvectorint dp(h, vectorint(w, MIN_VAL));for (int i 0;i h; i)dp[i][0] 0;for (int i 1; i w; i) {for (int j 0;j h; j) {for (auto d:Dir::dir){int px j d[0];int py i d[1];if (px 0 || py 0 || px h - 1 || py w - 1)continue; if (grid[px][py] grid[j][i])continue;dp[j][i] max(dp[j][i], dp[px][py] 1);}ans max(dp[j][i],ans);}}return ans;}
};记忆化搜索
class Solution {
public:struct Dir {constexpr static int dir[][2] {{-1,1},{0,1},{1,1}};};int dfs(int i, int j,vectorvectorint mem, const vectorvectorint grid){int m mem.size();int n mem[0].size();if (mem[i][j] ! -1)return mem[i][j];int ans 0;for (auto c:Dir::dir) {int nx i c[0];int ny j c[1];if ( nx 0 || nx m - 1 || ny 0 || ny n - 1)continue;if (grid[i][j] grid[nx][ny])continue;int t dfs(nx,ny, mem, grid);ans max(ans, 1 t);}return mem[i][j] ans;}int maxMoves(vectorvectorint grid) {int ans 0;int h grid.size();int w grid[0].size();vectorvectorint mem(h, vectorint(w, -1));for (int i 0;i h; i) {ans max(dfs(i, 0, mem, grid), ans);}return ans;}
};
