1368. 使网格图至少有一条有效路径的最小代价
分析题意:类似于两个岛屿之间的距离,思路可以为把从根节点能到达的节点都保存到队列,然后花费1,把队列修改为队列中的节点可以到达的节点群(岛屿),如果岛屿已经包含了目标,则可以退出了
//1368. 使网格图至少有一条有效路径的最小代价
// 从题意可知,从00出发必然到达目标节点有两种情况
// (1)可以直接到达,则返回0
// (2)无法直接到达,则需要返回cost
// //当无法直接到达时,从根节点可以到达一些节点,然后对这些节点花费cost=1,则扩充了新节点的可到达的所有节点
// 此时形成一个递归性质的层序遍历,终止条件为到达目标值,剪枝条件为是否已经访问过
public int minCost(int[][] grid) {
boolean[][] visited = new boolean[grid.length][grid[0].length];
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[]{0, 0});
int result = 0;
outer:
while (!queue.isEmpty()) {
int size = queue.size();
//对当前queue中的所有坐标作为起点进行dfs,查看能找到多少节点
for (int i = 0; i < size; i++) {
int[] cur = queue.poll();
dfs(grid, visited, queue, cur[0], cur[1]);
if (visited[grid.length - 1][grid[0].length - 1] == true) {
break outer;
}
}
//如果遍历之后还是没有发现,则需要对目前队列中的所有节点花费cost=1可以达到的点都加入到queue中
int size2 = queue.size();
for (int i = 0; i < size2; i++) {
int[] cur = queue.poll();
cost1(visited, queue, cur[0] + 1, cur[1]);
cost1(visited, queue, cur[0] - 1, cur[1]);
cost1(visited, queue, cur[0], cur[1] + 1);
cost1(visited, queue, cur[0], cur[1] - 1);
}
result++;
}
return result;
}
public void dfs(int[][] grid, boolean[][] visited, Queue<int[]> queue, int row, int col) {
if (row < 0 || row >= grid.length || col < 0 || col >= grid[0].length || visited[row][col] == true) {
return;
}
visited[row][col] = true;
queue.add(new int[]{row, col});
if (grid[row][col] == 1) {
dfs(grid, visited, queue, row, col + 1);
}
if (grid[row][col] == 2) {
dfs(grid, visited, queue, row, col - 1);
}
if (grid[row][col] == 3) {
dfs(grid, visited, queue, row + 1, col);
}
if (grid[row][col] == 4) {
dfs(grid, visited, queue, row - 1, col);
}
}
public void cost1(boolean[][] visited, Queue<int[]> queue, int row, int col) {
if (row < 0 || row >= visited.length || col < 0 || col >= visited[0].length || visited[row][col] == true) {
return;
}
queue.add(new int[]{row, col});
}