第4章万能的搜索-阿里云开发者社区

第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");
  }
  
}

}

第4章万能的搜索