深度优先搜索学习五例之四(JAVA)
先继续“深度优先搜索学习五例之三”http://128kj.iteye.com/admin/blogs/1702286中的迷宫,那里用栈实现了深搜,但只输出了一条路径,下面程序用递归实现深搜,输出所有到出口的路径和数目：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); System.out.println(); } } //深度优先搜索所有可能的路径 public void dfs(int x,int y){ Matrix=2; if(x == 8&& y == 7){ //输出找到的路径 total++; PrintMatrix(); } for(int i = 0; i<4; ++i){ //右下上左 int nx = x + x_off; int ny = y + y_off; if(nx >= 0 && nx < M && ny>=0 && ny< N && Matrix == 0){ dfs(nx,ny); } } Matrix =0;//这里就是回溯，很重要！！！}public int getTotal(){ return total;} //测试代码主函数 public static void main(String args[]) { MazeDsf maze=new MazeDsf(); maze.PrintMatrix(); maze.dfs(0,0); System.out.print("共有"+maze.getTotal()+"条路径"); } }
运行结果:
.........................................省略很多
入口(0,0),出口(8,7)的迷宫,2为通道,1为障碍:
21111111
20000000
21111010
22202210
01222210
01011210
01000211
01001222
01111102
入口(0,0),出口(8,7)的迷宫,2为通道,1为障碍:
21111111
20000000
21111010
22202210
01222210
01011210
01000211
01001220
01111122
.......................
共有72条路径
再看下面POJ1562:
题意：在一个n*m的地图上探索有多少块油田，'@'表示单位油田，相邻的(上下左右与对角线)单位油田为一个大油田，问有多少个大油田。
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; int mj = sj + move; if (mi >= m|| mj >= n || mi < 0 ||mj < 0) continue ; if (map == '@') { map = '*'; 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;for(int i=0;i<a;i++){ String s=in.next(); for(int j=0;j<b;j++) map=s.charAt(j);} Main m=new Main(a,b,map); int answer=0; for (int i = 0; i<a; i++) for (int j = 0; j<b; j++) if (map == '@') { map = '*'; m.DFS(i, j); ++answer; } System.out.printf("%d\n", answer); }}}
下载:
页:
[1]