题目大意：
使网格图至少有一条有效路径的最小代价
给你一个 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
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1368
解题思路分析：
我们之前的文章提到过多次，看到网格（矩阵）类型的题目，首选dfs或者bfs来解题，而本题是求最小cost问题，虽然不是求最小路径，但原理没有区别，因此解这类问题的最优选择当属bfs广度优先搜索。
使用bfs解题时，我们需要确定bfs起始条件，扩散规则以及bfs终止条件。与普通bfs题目不同，本题的难点就在于如何找到上述3个条件。首先题目给出了起点是左上角，因此，左上角坐标[0,0]一定是bfs起点之一，另外我们要知道，在不改变方向的前提下，从左上角能够到达的所有点与起点是同一级别的点，因为从起点到达这些点的花费都是0，因此我们可以将cost相同的点看做是同一级别的点，这些点也是我们bfs的起点。bfs每一步时，我们从这些点向外扩散一圈，能够覆盖到的点，以及与他们在同一级别上的所有点，都属于下一步bfs的范围，直到bfs范围能够覆盖到右下角位置，bfs的步数即是答案。
总结：
与普通的bfs不同，本题是将cost相同的所有点（利用题目给出的方向能够连接的所有点）看做为同一级别，这些点向外bfs扩散一圈，同时这一圈上所有的点以及与他们cost相同的点是bfs下一步的范围。这一点是本题最为精妙的地方！bfs每走一步，实际上是在级别不同的点之间做出了一次方向改变，使得他们级别相同。
实现代码：
boolean[][] visited; // 访问数组
// bfs的四个方向
int[][] dirs=new int[][]{{0,1},{0,-1},{1,0},{-1,0}};
public int minCost(int[][] grid) {
// 初始化访问数组
visited=new boolean[grid.length][grid[0].length];
// bfs用的Queue
Queue<int[]> q = new LinkedList<>();
// 将与右上角拥有相同cost的点加入Queue，作为bfs起点
findSameCost(q,grid,0,0);
// 返回结果
int res=0;
// bfs
while(q.size()>0){
// bfs每一步
int size=q.size();
while(size>0){
size--;
// 从Queue中取出一点
int[] node = q.poll();
// 如果该点是右下角，返回bfs步数
if(node[0]==grid.length-1&&node[1]==grid[0].length-1){
return res;
}
// 将当前点向四个方向扩散
for(int[]d : dirs){
// 得到扩散后的点坐标
int row = node[0]+d[0];
int col = node[1]+d[1];
// 将扩散后的点以及与它在同一cost上的点加入道Queue中
findSameCost(q,grid,row,col);
}
}
// 步数加一
res++;
}
return res;
}
// 找到与[row, col]为同一cost的所有点
void findSameCost(Queue<int[]> q,int[][] grid,int row,int col){
// 当前坐标没有越界并且没有访问过
while(row>=0&&row<grid.length
&&col>=0&&col<grid[0].length
&&!visited[row][col]){
// 将当前节点设置为已访问
visited[row][col]=true;
// 将当前点加入到Queue
q.offer(new int[]{row,col});
// 获得当前点能够走到的下一点坐标
int[] dir=dirs[grid[row][col]-1];
row+=dir[0];
col+=dir[1];
}
} 本题解法执行时间为8ms。
Runtime: 8 ms, faster than 99.74% of Java online submissions for Minimum Cost to Make at Least One Valid Path in a Grid.
Memory Usage: 41.5 MB, less than 100.00% of Java online submissions for Minimum Cost to Make at Least One Valid Path in a Grid.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1368-minimum-cost-to-make-at-least-one-valid-path-in-a-grid-解题思路分析/