九章算法 | 谷歌面经：迷宫

84 阅读 0 评论 56 点赞

我是靠谱客的博主鲜艳戒指，最近开发中收集的这篇文章主要介绍九章算法 | 谷歌面经：迷宫，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

描述

在迷宫中有一个球，里面有空的空间和墙壁。球可以通过滚上，下，左或右移动，

但它不会停止滚动直到撞到墙上。当球停止时，它可以选择下一个方向。

给定球的起始位置，目的地和迷宫，确定球是否可以停在终点。

迷宫由二维数组表示。1表示墙和0表示空的空间。你可以假设迷宫的边界都是墙。开始和目标坐标用行和列索引表示。

在迷宫中只有一个球和一个目的地。
球和目的地都存在于一个空的空间中，它们最初不会处于相同的位置。
给定的迷宫不包含边框(比如图片中的红色矩形)，但是你可以假设迷宫的边界都是墙。
迷宫中至少有2个空的空间，迷宫的宽度和高度都不会超过100。

在线评测地址

LintCode 领扣

样例1

输入:
map =
[
[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]
]
start = [0,4]
end = [3,2]
输出:
false

样例2

输入:
map =
[[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]
]
start = [0,4]
end = [4,4]
输出:
true

算法：BFS

简单的BFS。由于没有其他要求，我们只需要在BFS的过程中在队列里记录当前的坐标即可。

将地图的起点放入队列。
进行广度优先搜索。
- 每一次取出队首的元素，先判断是否到了终点，到了终点直接退出。
- 若没有到达，往四周的方向滚，直到滚到墙为止。若到达的位置没有被访问，那么加入队列中。
若整个过程都没有访问到终点，返回false即可。

上述也是一般BFS的执行过程。

复杂度分析

时间复杂度O(n∗m)O(n∗m)
有可能会遍历map上的每个点
空间复杂度O(n∗m)

public class Solution {
/**


* @param maze: the maze


* @param start: the start


* @param destination: the destination


* @return: whether the ball could stop at the destination


*/
public boolean hasPath(int[][] maze, int[] start, int[] destination) {
// write your code here

int n = maze.length;
int m = maze[0].length;
boolean[][] visited = new boolean[n][m];
int[] dx = new int[]{0, -1, 0, 1};
int[] dy = new int[]{1, 0, -1, 0};
Queue<int[]> queue = new LinkedList<>();
queue.offer(start);
visited[start[0]][start[1]] = true;
while (!queue.isEmpty()) {
int[] cur = queue.poll();
if (cur[0] == destination[0] && cur[1] == destination[1]) {
return true;
}
for (int direction = 0; direction < 4; direction++) {
int nx = cur[0], ny = cur[1];
while (nx >= 0 && nx < n && ny >= 0 && ny < m && maze[nx][ny] == 0) {
nx += dx[direction];
ny += dy[direction];
}
nx -= dx[direction];
ny -= dy[direction];
if (!visited[nx][ny]) {
visited[nx][ny] = true;
queue.offer(new int[]{nx, ny});
}
}
}
return false;
}
}