迷宫算法(ＪＡＶＡ实现)

对于走迷宫，人们提出过很多计算机上的解法。深度优先搜索、广度优先搜索是使用最广的方法。生活中，人们更愿意使用“紧贴墙壁，靠右行走”的简单规则。

下面的代码则采用了另一种不同的解法。它把走迷宫的过程比做“染色过程”。假设入口点被染为红色，它的颜色会“传染”给与它相邻的可走的单元。这个过程不断进行下去，如果最终出口点被染色，则迷宫有解。

在以下程序中“＃”代表不可通过，“．”代表可以通过。

public class Maze

{

class

Cell//内部类

{

private int row;

private int col;

private Cell from;//指向父节点

public Cell(int row, int col, Cell from)

{

this.row = row;

this.col = col;

this.from = from;

}

}

char[][]

maze =

{{'#','#','#','#','B','#','#','#','#','#','#','#'},

{'#','#','#','#','.','.','.','.','#','#','#','#'},

{'#','#','#','#','.','#','#','#','#','.','.','#'},

{'#','.','.','.','.','#','#','#','#','#','.','#'},

{'#','.','#','#','#','#','#','.','#','#','.','#'},

{'#','.','#','#','#','#','#','.','#','#','.','#'},

{'#','.','#','#','.','.','.','.','.','.','.','#'},

{'#','.','#','#','.','#','#','#','.','#','.','#'},

{'#','.','.','.','.','#','#','#','.','#','.','#'},

{'#','#','.','#','.','#','#','#','.','#','.','A'},

{'#','#','.','#','#','#','.','.','.','#','#','#'},

{'#','#','#','#','#','#','#','#','#','#','#','#'}};

public void

show()

{

for(int i=0; i

{

for(int j=0; j

System.out.print(" " + maze[i][j]);

System.out.println();

}

}

//把与from集合中相邻的可染色节点染色，被染色节点记入 dest

//一旦发现出口将被染色，则返回当前的“传播源”节点

public Cell

colorCell(Set from,

Set dest)

{

Iterator it =

from.iterator();

while(it.hasNext())

{

Cell a = it.next();

Cell[] c = new Cell[4];

c[0] = new Cell(a.row-1, a.col, a); //向上

c[1] = new Cell(a.row, a.col-1, a); //向左

c[2] = new Cell(a.row+1, a.col, a); //向下

c[3] = newCell(a.row, a.col+1, a); //向右

for(int i=0; i<4; i++)

{

if(c[i].row < 0 || c[i].row >=

maze.length)continue;

if(c[i].col < 0 || c[i].col >=

maze[0].length)continue;

char x = maze[c[i].row][c[i].col];

if(x=='B') return a;

if(x=='.')

{

maze[c[i].row][c[i].col] = '?';//对可通过路径进行标记

dest.add(c[i]);

}

}

}

return null;

}

public void

resolve()

{

Set set = new

HashSet();

set.add(new Cell(9,11,null));

for(;;)

{

Set set1 = new

HashSet();

Cell a = colorCell(set, set1);

if(a!=null)

{

System.out.println("找到解！");

while(a!=null)

{

maze[a.row][a.col] = '+';//标出通路路径

a =a.from;

}

break;

}

if(set1.isEmpty())

{

System.out.println("无解！");

break;

}

set = set1;

}

}

public

static void main(String[] args)

{

Maze m = new Maze();

m.show();

m.resolve();

m.show();

}

}

程序的输出结果为：＂＋＂代表通路

前几天参加字节跳动招聘的笔试，遇到了一个走迷宫的题目(笔试题目，就不挂原图了)，当时没有做出来，今天周末，上午总结了一下，来说一说这个迷宫到底怎么走

这篇文章将会分为三个部分，分别是：深度优先算法：获得一条路径

广度优先算法：获得最短路径的长度

广度优先算法：在有传送门的迷宫中寻找最短路径

一、深度优先算法：获得一条路径

在这个题目中，不涉及传送门，地图可以这样表示：

其中，1 的位置表示了墙，即不可使用，0 的位置则为路，因为现在值要求获得一条路径，是不是最佳路径我们不管，所以我们可以使用“一条路走到黑”的思路，深度优先。

(注：这里假设的启点为左上，重点为右下，在启点与重点非这种情形下，算法仍然适用)。

具体的做法是这样的：

首先我们先定义一个Position类来存储一下当前位置，也可以用数组，这里新建类是方便表示和理解：

class Position{

int row;

int cow;

public Position(int row,int cow){

this.cow = cow;

this.row = row;

}

public void show(){

System.out.println(this.row + " " + this.cow);

}

}

这里我还定义了一个show方法，是我在写的时候调试用的，大家可以不管或者直接删除。

然后我们需要设立一个栈，当然也可使用队列来存储这条路径，其次，我们还维护一个访问状态的二维数组，避免在一条圈上反复寻找，造成死循环。

public List solutionDFS(int[][] nums){

int rows = nums.length;

int cows = nums[0].length;

int[][] visited = new int[rows][cows];

Stack stack = new Stack<>();

Position p = new Position(0,0); // 记录一下当前位置，在启点 stack.add(p);

visited[0][0] = 1; // 访问状态设置为 1 ，代表已经访问过了 Position temp;

// 只要找到了终点就退出循环 // 始终没有找到，也会导致栈弹空 while (!stack.isEmpty()&& !(p.row == rows-1 && p.cow == cows-1)){

p = stack.peek(); // 获取上一个访问过的位置 // 按照方向 → ↓ ← ↑的顺序依次进行试探性的走一步 // 如果能走通(在迷宫范围内，不是墙，而且没有访问过，就可以认为是可以走) if (p.cow+1

temp = new Position(p.row,p.cow+1);

stack.add(temp);

visited[temp.row][temp.cow] = 1;

}else if (p.row+1

temp = new Position(p.row+1,p.cow);

stack.add(temp);

visited[temp.row][temp.cow] = 1;

}else if (p.cow-1>-1 && nums[p.row][p.cow-1] == 0 && visited[p.row][p.cow-1] != 1) {

temp = new Position(p.row,p.cow-1);

stack.add(temp);

visited[temp.row][temp.cow] = 1;

}else if (p.row-1 >-1 && nums[p.row-1][p.cow] == 0 && visited[p.row-1][p.cow] != 1){

temp = new Position(p.row-1,p.cow);

stack.add(temp);

visited[temp.row][temp.cow] = 1;

}else {

// 如果没有尝试了四个方向都没有走通，说明上一个点的选取有问题，直接弹出 stack.pop();

}

}

// 最后根据还在栈里的的元素，推导出一挑可用路径 if (stack.isEmpty()) return new LinkedList<>();

Deque deque = new LinkedList<>();

for (Position po:stack) {

deque.addLast(new int[]{po.row,po.cow});

}

return (List)deque;

}

这是针对上面的迷宫的一个输出：

路径比较长，我拆成了左右两个部分进行展示。

二、广度优先算法，获得最短路径

如果想要获得一条最短路径，那么我们可以使用广度优先的思路，“一层一层的剥开我的心”

！啊，回来！

广度优先的思路其实也很容易理解，拿到一个点后，根据这个点的步数，更新这个点周围四个方向上的最小步数，直到全局稳定(也就是没有更小值可以更新了)

public int solutionBFS(int[][] nums){

int rows = nums.length;

int cows = nums[0].length;

int[][] count = new int[rows][cows];

// 首先对计数的数组进行初始化 for (int i = 0;i

Arrays.fill(count[i],Integer.MAX_VALUE);

}

count[0][0] = 0;

// 由于深度优先算法是和遍历的层数有关的，所以我们使用双向链表来操作 // 前面添加，后面取用(还可以使用两个栈来进行交替使用) Deque deque = new LinkedList<>();

Position p = new Position(0,0);

deque.add(p);

int[] r = {0,1,0,-1};

int[] c = {1,0,-1,0};

while (!deque.isEmpty()){

p = deque.pollLast();

for (int i = 0; i<4;i++){

int tempR = p.row+r[i];

int tempC = p.cow+c[i];

if (tempR>-1 && tempR-1 && tempC

// 如果能够进行更新，那就将这个位置再次压入队列中，等待下一次更新 if (count[tempR][tempC] > count[p.row][p.cow]+1){

count[tempR][tempC] = count[p.row][p.cow]+1;

Position temp = new Position(tempR,tempC);

deque.addFirst(temp);

}

}

}

}

return count[rows-1][cows-1];

}

这是示例迷宫的输出：

由于和上面是一个地图，所以数过之后你会发现，确实最少路径是17步。

三、广度优先算法：在有传送门的迷宫中寻找最短路径

这是我们这次主要要说的迷宫，有传送门的迷宫。

一个示例的带有传送门的地图可能是这样的：

其中：

-2 表示启点，-3表示终点，0表示普通路径，-1表示墙，大于0的数字则表示传送门(能够保证传送门成对出现)。

我的思考过程是这样的：

由于传送门之间的穿送是不记录步数的，直觉的思路是：当遇到一个传送门时，直接传送，进而继续进行广度优先搜索(寻找最短路径)。

我认为这个思路可行，但是实现起来可能比较麻烦，因为：一方面，你不知道传送门用的顺序

另一方面，你不知道传送门使用的次数，可能是一次，也可能是0次。而广度优先，对一个点的访问极有可能更多次。

下面来说一下我的思路：

仍然是广度优先没有错，但是是两次，另外在两次之间，对传送门的步数取最小值：

public int solutionTransfer(int[][] nums){

int rows = nums.length;

int cows = nums[0].length;

HashMap> hashMap = new HashMap<>();

int endRow=0,endCow=0,startRow=0,startCow = 0;

// 先获得起始位置、终点位置，以及各个传送门的位置// 将传送门的代号和位置保存到hashmap中 for (int i = 0; i

for (int j = 0;j

if (nums[i][j] == -2){

startRow = i;

startCow = j;

}else if (nums[i][j] == -3){

endRow = i;

endCow = j;

}else {

if (nums[i][j]>0){

if ( !hashMap.containsKey(nums[i][j])){

List list = new LinkedList<>();

hashMap.put(nums[i][j],list);

}

hashMap.get(nums[i][j]).add(new int[]{i,j});

}

}

}

}

// 第一步广度优先算法 int[][] count = new int[rows][cows];

for (int i = 0;i

Arrays.fill(count[i],Integer.MAX_VALUE);

}

count[startRow][startCow] = 0;

Deque deque = new LinkedList<>();

Position p = new Position(startRow,startCow);

deque.add(p);

int[] r = {0,1,0,-1};

int[] c = {1,0,-1,0};

while (!deque.isEmpty()){

p = deque.pollLast();

for (int i = 0; i<4;i++){

int tempR = p.row+r[i];

int tempC = p.cow+c[i];

if (tempR>-1 && tempR-1 && tempC

if (count[tempR][tempC] > count[p.row][p.cow]+1){

count[tempR][tempC] = count[p.row][p.cow]+1;

Position temp = new Position(tempR,tempC);

deque.addFirst(temp);

}

}

}

}

// 通过hash来获得每一对传送门，嗖嗖嗖~ for (int targ : hashMap.keySet()){

List list = hashMap.get(targ);

int[] in = list.get(0);

int[] out = list.get(1);

if (count[in[0]][in[1]] < count[out[0]][out[1]]){

count[out[0]][out[1]] = count[in[0]][in[1]];

}else {

count[in[0]][in[1]] = count[out[0]][out[1]];

}

// 将更改过步数的路径继续压队列 // 这里的代码还可以优化，实际上只需要将原来大的那个点压入队列即可 // 也就是放到 if 和else 里面去，虽然看到了，但是，懒 deque.addFirst(new Position(in[0],in[1]));

deque.addFirst(new Position(out[0],out[1]));

}

// 新一轮的广度优先搜索，更新最小步骤数 while (!deque.isEmpty()){

p = deque.pollLast();

for (int i = 0; i<4;i++){

int tempR = p.row+r[i];

int tempC = p.cow+c[i];

if (tempR>-1 && tempR-1 && tempC

if (count[tempR][tempC] > count[p.row][p.cow]+1){

count[tempR][tempC] = count[p.row][p.cow]+1;

Position temp = new Position(tempR,tempC);

deque.addFirst(temp);

}

}

}

}

// 返回最小步骤数 return count[endRow][endCow];

}

针对给出的示例迷宫(带有传送门)，测试结果是这样的：

感谢评论区 @华樱 指出的问题，对上面第三个问题做了一点点改动，改动代码如下：

public int solutionTransferS(int[][] nums){

int rows = nums.length;

int cows = nums[0].length;

HashMap> hashMap = new HashMap<>();

int endRow=0,endCow=0,startRow=0,startCow = 0;

// 先获得起始位置、终点位置，以及各个传送门的位置// 将传送门的代号和位置保存到hashmap中 for (int i = 0; i

for (int j = 0;j

if (nums[i][j] == -2){

startRow = i;

startCow = j;

}else if (nums[i][j] == -3){

endRow = i;

endCow = j;

}else {

if (nums[i][j]>0){

if ( !hashMap.containsKey(nums[i][j])){

List list = new LinkedList<>();

hashMap.put(nums[i][j],list);

}

hashMap.get(nums[i][j]).add(new int[]{i,j});

}

}

}

}

int[][] count = new int[rows][cows];

for (int i = 0;i

Arrays.fill(count[i],Integer.MAX_VALUE);

}

count[startRow][startCow] = 0;

Position p = new Position(startRow,startCow);

Deque deque = new LinkedList<>();

deque.addFirst(p);

List list;

int[] r = {0,1,0,-1};

int[] c = {1,0,-1,0};

while (!deque.isEmpty()){

p = deque.pollLast();

for (int i = 0; i<4;i++){

int tempR = p.row+r[i];

int tempC = p.cow+c[i];

if (tempR>-1 && tempR-1 && tempC

if (nums[p.row][p.cow] >0 && nums[tempR][tempC] == nums[p.row][p.cow]){

continue;

}

if (count[tempR][tempC] > count[p.row][p.cow]+1){

count[tempR][tempC] = count[p.row][p.cow]+1;

Position temp = new Position(tempR,tempC);

deque.addFirst(temp);

}

}

}

if (hashMap.containsKey(nums[p.row][p.cow])){

list = hashMap.get(nums[p.row][p.cow]);

for (int[] t:list) {

if (p.row!=t[0] || p.cow!=t[1]){

if (count[t[0]][t[1]] > count[p.row][p.cow]){

count[t[0]][t[1]] = count[p.row][p.cow];

p.row = t[0];

p.cow = t[1];

deque.addFirst(p);

}

break;

}

}

}

}

return count[endRow][endCow];

}

至于仍然存在的代码冗余问题，确实是还没理解足够透彻，欢迎大家继续挑毛病。

想要获得全部代码，欢迎到我的仓库：PluteW/InterviewCode​github.com