网站建设要素,专题网站开发工具,优化工具箱,上海网站排名优化公司1. 题目
给你一个 m x n 的网格图 grid 。 grid 中每个格子都有一个数字#xff0c;对应着从该格子出发下一步走的方向。 grid[i][j] 中的数字可能为以下几种情况#xff1a;
1 #xff0c;下一步往右走#xff0c;也就是你会从 grid[i][j] 走到 grid[i][j 1]2 #xf…1. 题目
给你一个 m x n 的网格图 grid 。 grid 中每个格子都有一个数字对应着从该格子出发下一步走的方向。 grid[i][j] 中的数字可能为以下几种情况
1 下一步往右走也就是你会从 grid[i][j] 走到 grid[i][j 1]2 下一步往左走也就是你会从 grid[i][j] 走到 grid[i][j - 1]3 下一步往下走也就是你会从 grid[i][j] 走到 grid[i 1][j]4 下一步往上走也就是你会从 grid[i][j] 走到 grid[i - 1][j] 注意网格图中可能会有 无效数字 因为它们可能指向 grid 以外的区域。
一开始你会从最左上角的格子 (0,0) 出发。我们定义一条 有效路径 为从格子 (0,0) 出发每一步都顺着数字对应方向走最终在最右下角的格子 (m - 1, n - 1) 结束的路径。有效路径 不需要是最短路径 。
你可以花费 cost 1 的代价修改一个格子中的数字但每个格子中的数字 只能修改一次 。
请你返回让网格图至少有一条有效路径的最小代价。
示例 1
输入grid [[1,1,1,1],[2,2,2,2],[1,1,1,1],[2,2,2,2]]
输出3
解释你将从点 (0, 0) 出发。
到达 (3, 3) 的路径为 (0, 0) -- (0, 1) -- (0, 2) -- (0, 3)
花费代价 cost 1 使方向向下 -- (1, 3) -- (1, 2) -- (1, 1) -- (1, 0)
花费代价 cost 1 使方向向下 -- (2, 0) -- (2, 1) -- (2, 2) -- (2, 3)
花费代价 cost 1 使方向向下 -- (3, 3)
总花费为 cost 3.示例 2
输入grid [[1,1,3],[3,2,2],[1,1,4]]
输出0
解释不修改任何数字你就可以从 (0, 0) 到达 (2, 2) 。示例 3
输入grid [[1,2],[4,3]]
输出1示例 4
输入grid [[2,2,2],[2,2,2]]
输出3示例 5
输入grid [[4]]
输出0提示
m grid.length
n grid[i].length
1 m, n 100来源力扣LeetCode 链接https://leetcode-cn.com/problems/minimum-cost-to-make-at-least-one-valid-path-in-a-grid 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
2. 解题
BFS广度优先搜索最短路径将箭头可以走到的地方全部加入队列并标记访问过然后将队列里的取出向4个方向反转路径并一路添加新的没访问的可走点
class Solution {
public:int minCost(vectorvectorint grid) {int m grid.size(), n grid[0].size();int i, j, x 0, y 0, a, b, k, flip 0, size;vectorvectorint dir {{0,0},{0,1},{0,-1},{1,0},{-1,0}};vectorvectorbool visited(m,vectorbool(n,false));queuepairint,int q;while(x0 xm y0 yn !visited[x][y]){q.push({x,y});visited[x][y] true;i x dir[grid[x][y]][0];j y dir[grid[x][y]][1];x i, y j;}if(visited[m-1][n-1])return 0;while(!q.empty()){size q.size();flip;while(size--){i q.front().first;j q.front().second;q.pop();for(k 1; k 4; k){x i dir[k][0];y j dir[k][1];while(x0 xm y0 yn !visited[x][y]){q.push({x,y});visited[x][y] true;a x dir[grid[x][y]][0];b y dir[grid[x][y]][1];x a, y b;}}}if(visited[m-1][n-1])return flip;}return flip;}
};
