第4章 万能的搜索
第1节 不撞南墙不回头–深度优先搜索
3.4的全排列问题。
考虑这样解决：如果有k个数要排列，就会排出k位数。
把k位当成k个盒子，k个数当成k张扑克牌，排列的过程就是依次往盒子里放扑克牌。（高中时的排列组合好像经常会这么做）
这种放扑克牌的过程，可以使用深度优先搜索。
深度优先的基本模型：
void dfs(int step) { 判断边界 尝试每一种可能 for() { 继续下一步dfs(step+1) } 返回 }
//n个数的全排列，n范围是1-9 package ch4; import java.util.Scanner; public class DFSTest { public int[] a =new int[10];//盒子 public int[] book=new int[10];//标记扑克牌是否在手上，0代表在 public int n; void dfs(int step) { //判断边界 if(step==this.n+1) { for(int i=1;i<=n;i++) { System.out.print(a[i]); } System.out.println(); return ; } //尝试每一种可能 for(int i=1;i<=n;i++) { if(book[i]==0) { //牌在手上，放入盒子中 a[step]=i; book[i]=1; dfs(step+1);//放完第step个盒子，继续放下一个 book[i]=0;//收回刚刚放的扑克牌，用来下次尝试 } } return; } public static void main(String[] args) { DFSTest t = new DFSTest(); Scanner sc = new Scanner(System.in); t.n = sc.nextInt(); t.dfs(1); } }
第2节 解救小哈
迷宫里找到小哈
//迷宫两点最近路径，原题只给出最近路径的值，没给出路径。 //在min=setp处（26行）,可以同时记录最短路径 package ch4; import java.util.Scanner; public class DFSTest3 { int p,q; int n,m; int[][] a = new int[51][51];//迷宫 int[][] book = new int[51][51];//路径 int min = 99999; int[][] map = new int[51][51]; int[][]minmap = new int[51][51]; void dfs(int x,int y,int step) { //方向，右下左上 int[][] next= {{0,1}, {1,0}, {0,-1}, {-1,0}}; int tx,ty,k; if(x==p&&y==q) { if(step<min) { min=step; //记录当前路径 for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { minmap[i][j] = book[i][j]; } } } return; } //尝试每一种走法 for(k=0;k<=3;k++) { tx = x+next[k][0]; ty = y+next[k][1]; //越界 if(tx<1||tx>n||ty<1||ty>m) { continue; } //点不在障碍物上且 没有走过 if(a[tx][ty]==0&&book[tx][ty]==0) { book[tx][ty]=1; dfs(tx,ty,step+1); book[tx][ty]=0; } } return; } public static void main(String[] args) { DFSTest3 t = new DFSTest3(); Scanner sc = new Scanner(System.in); t.n = sc.nextInt(); t.m = sc.nextInt(); for(int i=1;i<=t.n;i++) { for(int j=1;j<=t.m;j++) { t.a[i][j]=sc.nextInt(); } } int startx =sc.nextInt(); int starty= sc.nextInt(); t.p = sc.nextInt(); t.q = sc.nextInt(); t.book[startx][starty]=1; t.dfs(startx,starty,0); System.out.println(t.min); for(int i=1;i<=t.n;i++) { for(int j=1;j<=t.m;j++) { System.out.print(t.minmap[i][j]+" "); } System.out.println(); } } }
第3节 层层递进–广度优先算法
BFS（breadth first search）
和第2节的深度优先搜索不同，这里使用广度优先不是一直往下找直到找到路为止，而是“一层一层”地寻找，第一次把一步能走到的点都加入队列，第二步利用第一步的点，把两步能走到的点都加入队列，直到小哈被找到就停止扩展。
package ch4; import java.util.Scanner; public class BFSTest1 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); node[] que = new node[2501]; for(int i=0;i<que.length;i++) { que[i] = new node(); } int [][]a = new int[51][51]; int [][]book = new int[51][51]; //方向，右下左上 int[][] next= {{0,1}, {1,0}, {0,-1}, {-1,0}}; int head,tail; int n = sc.nextInt(); int m = sc.nextInt(); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { a[i][j] = sc.nextInt(); } } int startx = sc.nextInt(); int starty = sc.nextInt(); int p = sc.nextInt(); int q = sc.nextInt(); head =1; tail =1; //队列插入入口坐标 que[tail].x=startx; que[tail].y=starty; que[tail].f = 0; que[tail].step = 0; tail++; book[startx][starty]=1; int flag =0;//是否到达目标点，0表示没有到达。 //队列不为空(还有点可以扩展)时循环 while(head<tail) { //尝试4种方向 for(int k=0;k<=3;k++) { int tx = que[head].x+next[k][0]; int ty = que[head].y+next[k][1]; //判断越界 if(tx<1||tx>n||ty<1||ty>m) { continue; } //判断障碍物或是否在路径 if(a[tx][ty]==0&&book[tx][ty]==0) { book[tx][ty]=1; que[tail].x=tx; que[tail].y =ty; que[tail].f =head; que[tail].step=que[head].step+1; tail++; } //找到目标，停止 if(tx==p&&ty==q) { flag =1; break; } } if(flag==1) { break; } head++; //当一个扩展点结束后，head++才能对后面的点进行扩展 } System.out.println(que[tail-1].step); } } class node{ int x; int y; int f; //父亲在队列中的编号 int step; }
第4节 再解炸弹人
第3章第2节中的炸弹人问题，求在哪个位置放炸弹消灭敌人最多，求出来的地点可能是炸弹人走不到的，利用本章的搜索可以先找出可以到达的点，再枚举。
第5节 宝岛探险
求解从某个点出发，能到达的全部地点。
和迷宫基本一样。
着色法，只需要在走的过程中加入染色过程a[x][y]=color
找到地图上所有的独立小岛：只需要对每一个大于0（没染色的陆地）的点进行一次深度优先搜索。
测试数据，答案为4 10 10 1 2 1 0 0 0 0 0 2 3 3 0 2 0 1 2 1 0 1 2 4 0 1 0 1 2 3 2 0 1 3 2 0 0 0 1 2 4 0 0 0 0 0 0 0 0 1 5 3 0 0 1 2 1 0 1 5 4 3 0 0 1 2 3 1 3 6 2 1 0 0 0 3 4 8 9 7 5 0 0 0 0 0 3 7 8 6 0 1 2 0 0 0 0 0 0 0 0 1 0
package ch4; import java.util.Scanner; public class DFSTest5 { int sum; int n,m; int[][] a = new int[51][51];//迷宫 int[][] book = new int[51][51];//路径 void dfs(int x,int y,int color) { //方向，右下左上 int[][] next= {{0,1}, {1,0}, {0,-1}, {-1,0}}; int tx,ty,k; a[x][y] = color; //染色 //尝试每一种走法 for(k=0;k<=3;k++) { tx = x+next[k][0]; ty = y+next[k][1]; //越界 if(tx<1||tx>n||ty<1||ty>m) { continue; } //点在陆地上且 没有走过 if(a[tx][ty]>0 &&book[tx][ty]==0) { sum++; book[tx][ty]=1; dfs(tx,ty,color); } } return; } public static void main(String[] args) { DFSTest5 t = new DFSTest5(); Scanner sc = new Scanner(System.in); t.n = sc.nextInt(); t.m = sc.nextInt(); for(int i=1;i<=t.n;i++) { for(int j=1;j<=t.m;j++) { t.a[i][j]=sc.nextInt(); } } int num = 0;//染色的颜色 for(int i=1;i<=t.n;i++) { for(int j=1;j<=t.m;j++) { if(t.a[i][j]>0) { num--; t.book[i][j]=1; t.dfs(i, j, num); } } } for(int i=1;i<=t.n;i++) { for(int j=1;j<=t.m;j++) { System.out.printf("%3d",t.a[i][j]); } System.out.println(); } System.out.println("共有"+(-num)+"个小岛"); } }
第6节 水管工游戏
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Cg7LbWF6-1589449662208)(C:\Users\LF\AppData\Roaming\Typora\typora-user-images\1588902125296.png)]
可以使用深度优先搜索解决，
过程类似走迷宫，但是当前一步要根据上一步的管子方向确定，而且相应的下一步的位置也被当前一步的管子方向决定。
package ch4; import java.util.Scanner; public class DFSTest6 { class node { int x; int y; node(int x,int y){ this.x=x; this.y=y; } } int n,m; int flag; int top=0; int [][]book = new int[51][51]; int [][]a = new int[51][51]; node[] s = new node[100]; void dfs(int x,int y,int front) { if(x==n&&y==m+1) { flag = 1; for(int i=1;i<=top;i++) { System.out.printf("(%d,%d) ",s[i].x,s[i].y); } return; } //判断越界 if(x<1 || x>n || y<1 || y>m) { return ; } //判断已经使用过 if(book[x][y]==1) { return; } book[x][y]=1; top++; s[top] = new node(x,y); //当前水管是直管 5/6 if(a[x][y]>=5&&a[x][y]<=6) { if(front==1) { //进水口在左边 dfs(x,y+1,1); } if(front==2) { //进水口在上边 dfs(x+1,y,2); } if(front==3) {//进水口在右边 dfs(x,y-1,3); } if(front==4) {//进水口在下边 dfs(x-1,y,4); } } //水管是弯管 if(a[x][y]>=1&&a[x][y]<=4) { if(front==1) { //进水口在左边 dfs(x+1,y,2); dfs(x-1,y,4); } if(front==2) { //进水口在上边 dfs(x,y+1,2); dfs(x,y-1,3); } if(front==3) {//进水口在右边 dfs(x-1,y,4); dfs(x+1,y,2); } if(front==4) {//进水口在下边 dfs(x,y+1,1); dfs(x,y-1,3); } } book[x][y]=0; top--; return; } public static void main(String[] args) { DFSTest6 t = new DFSTest6(); Scanner sc = new Scanner(System.in); t.n=sc.nextInt(); t.m=sc.nextInt(); for(int i=1;i<=t.n;i++) { for(int j=1;j<=t.m;j++) { t.a[i][j]=sc.nextInt(); } } t.dfs(1,1,1); if(t.flag==0) { System.out.println("impossible"); } } }
) {//进水口在下边
dfs(x,y+1,1);
dfs(x,y-1,3);
}
}
book[x][y]=0;
top–;
return;
} public static void main(String[] args) { DFSTest6 t = new DFSTest6(); Scanner sc = new Scanner(System.in); t.n=sc.nextInt(); t.m=sc.nextInt(); for(int i=1;i<=t.n;i++) { for(int j=1;j<=t.m;j++) { t.a[i][j]=sc.nextInt(); } } t.dfs(1,1,1); if(t.flag==0) { System.out.println("impossible"); } }
}
