# 一种新的走迷宫的方法

对于走迷宫，人们提出过很多计算机上的解法。深度优先搜索、广度优先搜索是使用最广的方法。

example:

```#include "stdio.h"
#define M 4

#define N 4

int matrix[N+2][M+2] = {
{1,1,1,1,1,1},
{1,0,0,0,1,1},
{1,0,1,0,0,1},
{1,0,0,0,1,1},
{1,1,0,0,0,1},
{1,1,1,1,1,1}
};

int path[20][2];
//出口坐标
int eX = 4;
int eY = 4;
int sX = 1;//进口坐标
int sY = 1;

int dir[4][2] = {
{-1,0},//上
{1,0},//下
{0,-1},//左
{0,1}//右
};

int count = 1;
void go (int x,int y) {
int i;
path[count][0] = x;
path[count][1] = y;
matrix[x][y] = count;
count++;
if (x == eX && y == eY) {
int j;
printf ("step = %d\n",count-1);
for (j = 1;j < count;j++) {
printf ("(%d,%d) ",path[j][0],path[j][1]);
if (j % 4 == 0) {
printf ("\n");
}
}
printf ("\n\n");
}else {
for (i = 0;i < 4;i++) {
int newX = x + dir[i][0];
int newY = y + dir[i][1];
if (matrix[newX][newY] == 0) {
go (newX,newY);
}
}
}
count--;
matrix[x][y] = 0;
}
int main () {
go (sX,sY);
return 0;
}

step = 7
(1,1) (2,1) (3,1) (3,2)
(4,2) (4,3) (4,4)

step = 7
(1,1) (2,1) (3,1) (3,2)
(3,3) (4,3) (4,4)

step = 7
(1,1) (1,2) (1,3) (2,3)
(3,3) (4,3) (4,4)

step = 9
(1,1) (1,2) (1,3) (2,3)
(3,3) (3,2) (4,2) (4,3)
(4,4)

```

```import java.util.*;
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<maze.length; i++)
{
for(int j=0; j<maze[i].length; j++)
System.out.print(" " + maze[i][j]);
System.out.println();
}
}

//把与from集合中相邻的可染色节点染色，被染色节点记入 dest
//一旦发现出口将被染色，则返回当前的“传播源”节点
public Cell colorCell(Set<Cell> from, Set<Cell> dest)
{
Iterator<Cell> 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] = new Cell (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] = '?';//染色了
}
}
}
return null;
}

public void resolve()
{
Set<Cell> set = new HashSet<Cell>();

for(;;)
{
Set<Cell> set1 = new HashSet<Cell>();//被染色的
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();
}
}
```

``` # # # # B # # # # # # #
# # # # . . . . # # # #
# # # # . # # # # . . #
# . . . . # # # # # . #
# . # # # # # . # # . #
# . # # # # # . # # . #
# . # # . . . . . . . #
# . # # . # # # . # . #
# . . . . # # # . # . #
# # . # . # # # . # . A
# # . # # # . . . # # #
# # # # # # # # # # # #

# # # # B # # # # # # #
# # # # + . . . # # # #
# # # # + # # # # ? ? #
# + + + + # # # # # ? #
# + # # # # # ? # # ? #
# + # # # # # ? # # ? #
# + # # + + + + + + + #
# + # # + # # # ? # + #
# + + + + # # # ? # + #
# # ? # ? # # # ? # + +
# # ? # # # ? ? ? # # #
# # # # # # # # # # # #
```

A为入口：B为出口！