# 深度优先搜索学习五例之四(JAVA)

```import java.util.Stack;
////////////////////////////////////////////////
//深度优先搜索之迷宫问题:输出所有到出口的路径
public class MazeDsf{
private static final int M=9;
private static final int N=8;
private int total;

//迷宫矩阵,0为通道，1为障碍
//入口(0,0),出口(8,7)
private int[][] Matrix = {
{ 0, 1, 1, 1, 1, 1, 1, 1 },
{ 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 1, 1, 1, 1, 0, 1, 0 },
{ 0, 0, 0, 0, 0, 0, 1, 0 },
{ 0, 1, 0, 0, 0, 0, 1, 0 },
{ 0, 1, 0, 1, 1, 0, 1, 0 },
{ 0, 1, 0, 0, 0, 0, 1, 1 },
{ 0, 1, 0, 0, 1, 0, 0, 0 },
{ 0, 1, 1, 1, 1, 1, 0, 0 } };

public MazeDsf(){
total=0;
}

//右下上左
private int x_off[] = {0,1,-1,0};
private int y_off[] = {1,0,0,-1};

//输出迷宫
private void PrintMatrix(){
System.out.println("入口(0,0),出口(8,7)的迷宫,2为通道,1为障碍:");
for(int i = 0; i < M; ++i){
for(int j = 0; j < N; ++j)
System.out.print(Matrix[i][j]);
System.out.println();
}
}
//深度优先搜索所有可能的路径
public void dfs(int x,int y)
{
Matrix[x][y]=2;
if(x == 8&& y == 7){
//输出找到的路径
total++;
PrintMatrix();

}

for(int i = 0; i<4; ++i){ //右下上左
int nx = x + x_off[i];
int ny = y + y_off[i];
if(nx >= 0 && nx < M && ny>=0 && ny< N && Matrix[nx][ny] == 0){
dfs(nx,ny);
}
}
Matrix[x][y] =0;//这里就是回溯，很重要！！！
}

public int getTotal(){
}

//测试代码主函数
public static void main(String args[]) {
MazeDsf maze=new MazeDsf();
maze.PrintMatrix();
maze.dfs(0,0);
System.out.print("共有"+maze.getTotal()+"条路径");
}
} ```

.........................................省略很多

21111111
20000000
21111010
22202210
01222210
01011210
01000211
01001222
01111102

21111111
20000000
21111010
22202210
01222210
01011210
01000211
01001220
01111122
.......................

Sample Input

1 1
*
3 5
*@*@*
**@**
*@*@*
1 8
@@****@*
5 5
****@
*@@*@
*@**@
@@@*@
@@**@
0 0
Sample Output

0
1
2
2

就是求多少个连通分量，顺序扫描，每扫面到一个@，并且这个格子没有被深度遍历过，就进行一次深度优先遍历.

```import java.util.Scanner;
public class Main{
int m, n;
char map[][];
int move[][] = { {-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1} };

public Main(int m,int n,char[][] map){
this.m=m;
this.n=n;
this.map=map;

}

private void DFS(int si, int sj) {

for (int i = 0; i<8; ++i) {
int mi = si + move[i][0];
int mj = sj + move[i][1];
if (mi >= m|| mj >= n || mi < 0 ||mj < 0) continue ;
if (map[mi][mj] == '@') {
map[mi][mj] = '*';
DFS(mi, mj);
}
}
return ;
}

public static void main(String args[]){
Scanner in=new Scanner(System.in);
while(true){
int a=in.nextInt();
int b=in.nextInt();
if(a==0&&b==0)break;
int count=0;
char[][] map=new char[a][b];
for(int i=0;i<a;i++){
String s=in.next();
for(int j=0;j<b;j++)
map[i][j]=s.charAt(j);
}
Main m=new Main(a,b,map);
for (int i = 0; i<a; i++)
for (int j = 0; j<b; j++)
if (map[i][j] == '@') {
map[i][j] = '*';
m.DFS(i, j);
}

}
}
}
```

• 0

开心

• 0

板砖

• 0

感动

• 0

有用

• 0

疑问

• 0

难过

• 0

无聊

• 0

震惊