Q：由空地和墙组成的迷宫中有一个球。球可以向上下左右四个方向滚动，但在遇到墙壁前不会停止滚动。当球停下时，可以选择下一个方向。
给定球的起始位置，目的地和迷宫，判断球能否在目的地停下。
迷宫由一个0和1的二维数组表示。 1表示墙壁，0表示空地。你可以假定迷宫的边缘都是墙壁。起始位置和目的地的坐标通过行号和列号给出。
示例 1:
输入 1: 迷宫由以下二维数组表示
0 0 1 0 0
0 0 0 0 0
0 0 0 1 0
1 1 0 1 1
0 0 0 0 0
输入 2: 起始位置坐标 (rowStart, colStart) = (0, 4)
输入 3: 目的地坐标 (rowDest, colDest) = (4, 4)
输出: true
解析: 一个可能的路径是 : 左 -> 下 -> 左 -> 下 -> 右 -> 下 -> 右。
示例 2:
输入 1: 迷宫由以下二维数组表示
0 0 1 0 0
0 0 0 0 0
0 0 0 1 0
1 1 0 1 1
0 0 0 0 0
输入 2: 起始位置坐标 (rowStart, colStart) = (0, 4)
输入 3: 目的地坐标 (rowDest, colDest) = (3, 2)
输出: false
解析: 没有能够使球停在目的地的路径。
A：DFS和BFS双解。
DFS：我们从起始位置开始，每次选择一条路线进行搜索，并用一个二维布尔数组 visited 表示是否曾经到达过位置 (i, j) ，若在某一次搜索到位置 (i, j) 时，visited[i, j] = true，那么我们可以进行回溯，不必继续搜索下去。
public boolean hasPath(int[][] maze, int[] start, int[] destination) {
boolean[][] visited = new boolean[maze.length][maze[0].length];
for (int i = 0; i < maze.length; i++) {
Arrays.fill(visited[i], false);
}
return dfs(maze, start[0], start[1], destination, visited);
}
private boolean dfs(int[][] maze, int x, int y, int[] destination, boolean[][] visited) {
//走过，说明该位置所有情况都考虑了一遍但找不到出路
if (visited[x][y])
return false;
if (x == destination[0] && y == destination[1])
return true;
visited[x][y] = true;
int r = y + 1, l = y - 1, u = x - 1, d = x + 1;
int m = maze.length, n = maze[0].length;
//右走到头后所有结果都走一遍
while (r < n && maze[x][r] == 0)
r++;
if (dfs(maze, x, r - 1, destination, visited))
return true;
//左走到头后所有结果都走一遍
while (l >= 0 && maze[x][l] == 0)
l--;
if (dfs(maze, x, l + 1, destination, visited))
return true;
//上走到头后所有结果都走一遍
while (u >= 0 && maze[u][y] == 0)
u--;
if (dfs(maze, u + 1, y, destination, visited))
return true;
//下走到头后所有结果都走一遍
while (d < m && maze[d][y] == 0)
d++;
if (dfs(maze, d - 1, y, destination, visited))
return true;
//上下左右都没法找到出路
return false;
}
BFS:同样用一个visited把走过的记下来
private int[] idx = {-1, 0, 1, 0, -1};
public boolean hasPath(int[][] maze, int[] start, int[] destination) {
int m = maze.length, n = maze[0].length;
boolean[][] visited = new boolean[m][n];
for (int i = 0; i < maze.length; i++) {
Arrays.fill(visited[i], false);
}
Queue<int[]> q = new LinkedList<>();
q.add(start);
while (!q.isEmpty()) {
int[] curr = q.poll();
int x = curr[0];
int y = curr[1];
visited[x][y] = true;
if (x == destination[0] && y == destination[1])
return true;
for (int k = 0; k < 4; k++) {
int nx = x + idx[k];
int ny = y + idx[k+1];
while (nx >= 0 && ny >= 0 && nx < maze.length && ny < maze[0].length && maze[nx][ny] == 0) {
nx = nx + idx[k];
ny = ny + idx[k+1];
}
nx = nx - idx[k];
ny = ny - idx[k+1];
if(visited[nx][ny])
continue;
q.add(new int[]{nx, ny});
}
}
return false;
}
Q：由空地和墙组成的迷宫中有一个球。球可以向上下左右四个方向滚动，但在遇到墙壁前不会停止滚动。当球停下时，可以选择下一个方向。
给定球的起始位置，目的地和迷宫，找出让球停在目的地的最短距离。距离的定义是球从起始位置（不包括）到目的地（包括）经过的空地个数。如果球无法停在目的地，返回 -1。
迷宫由一个0和1的二维数组表示。 1表示墙壁，0表示空地。你可以假定迷宫的边缘都是墙壁。起始位置和目的地的坐标通过行号和列号给出。
示例 1:
输入 1: 迷宫由以下二维数组表示
0 0 1 0 0
0 0 0 0 0
0 0 0 1 0
1 1 0 1 1
0 0 0 0 0
输入 2: 起始位置坐标 (rowStart, colStart) = (0, 4)
输入 3: 目的地坐标 (rowDest, colDest) = (4, 4)
输出: 12
解析: 一条最短路径 : left -> down -> left -> down -> right -> down -> right。
总距离为 1 + 1 + 3 + 1 + 2 + 2 + 2 = 12。
示例 2:
输入 1: 迷宫由以下二维数组表示
0 0 1 0 0
0 0 0 0 0
0 0 0 1 0
1 1 0 1 1
0 0 0 0 0
输入 2: 起始位置坐标 (rowStart, colStart) = (0, 4)
输入 3: 目的地坐标 (rowDest, colDest) = (3, 2)
输出: -1
解析: 没有能够使球停在目的地的路径。
A：同样DFS和BFS双解。
DFS：可以使用深度优先搜索对整颗搜索树进行遍历。我们从起始位置开始，每次选择一条路线进行搜索，并用计数器 count 记录当前的步数。为了防止重复搜索，我们需要使用一个二维数组 distance 记录从起始位置到 (i, j) 的最小步数 distance[i, j]，若在某一次搜索到位置 (i, j) 时，distance[i, j] 的值小于等于 count，那么我们可以进行回溯，不必继续搜索下去。
private int[] idx = {-1, 0, 1, 0, -1};
public int shortestDistance(int[][] maze, int[] start, int[] destination) {
int[][] distence = new int[maze.length][maze[0].length];
for (int i = 0; i < maze.length; i++) {
Arrays.fill(distence[i], Integer.MAX_VALUE);
}
distence[start[0]][start[1]] = 0;
dfs(maze, start[0], start[1], destination, 0, distence);
return distence[destination[0]][destination[1]] == Integer.MAX_VALUE
? -1 : distence[destination[0]][destination[1]];
}
private void dfs(int[][] maze, int x, int y, int[] destination, int count, int[][] distence) {
for (int k = 0; k < 4; k++) {
int newCount = count;
int nx = x + idx[k];
int ny = y + idx[k + 1];
while (nx >= 0 && ny >= 0 && nx < maze.length && ny < maze[0].length && maze[nx][ny] == 0) {
newCount++;
nx = nx + idx[k];
ny = ny + idx[k + 1];
}
nx = nx - idx[k];
ny = ny - idx[k + 1];
if (newCount<distence[nx][ny]){
distence[nx][ny] = newCount;
dfs(maze, nx, ny, destination, newCount, distence);
}
}
}
BFS:在一般的广度优先搜索中，我们不会经过同一个节点超过一次，但在这道题目中，只要从起始位置到当前节点的步数 count 小于之前记录的最小步数 distance[i, j]，我们就会把 (i, j) 再次加入队列中。
private int[] idx = {-1, 0, 1, 0, -1};
public int shortestDistance(int[][] maze, int[] start, int[] destination) {
int[][] distence = new int[maze.length][maze[0].length];
for (int i = 0; i < maze.length; i++) {
Arrays.fill(distence[i], Integer.MAX_VALUE);
}
distence[start[0]][start[1]] = 0;
Queue<int[]> q = new LinkedList<>();
q.add(new int[]{start[0], start[1]});
while (!q.isEmpty()) {
int[] curr = q.poll();
int x = curr[0];
int y = curr[1];
for (int k = 0; k < 4; k++) {
int newCount = distence[x][y];
int nx = x + idx[k];
int ny = y + idx[k + 1];
while (nx >= 0 && ny >= 0 && nx < maze.length && ny < maze[0].length && maze[nx][ny] == 0) {
newCount++;
nx = nx + idx[k];
ny = ny + idx[k + 1];
}
nx = nx - idx[k];
ny = ny - idx[k + 1];
if (newCount < distence[nx][ny]) {
distence[nx][ny] = newCount;
q.add(new int[]{nx, ny});
}
}
}
return distence[destination[0]][destination[1]] == Integer.MAX_VALUE
? -1 : distence[destination[0]][destination[1]];
}