深搜广搜算法

发表于 分类于 阅读次数： 本文字数： 955 阅读时长 ≈ 3 分钟

深搜

全排列

现有n个字符，要求进行全排列，比如abc三个字符，则有abc，acb，bac，bca，cab，cba，6种排列。

java代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public class Main{
  private static char[] arr;//待全排列字符数组
  private static char[] box;//盒子
  private static boolean[] flag;//标记
  public static void main(String[] args) throws Exception {
    Scanner in = new Scanner(System.in);
    int n = in.nextInt();
    arr = new char[n];
    box = new char[n];
    flag = new boolean[n];
    for(int i = 0; i < n; i++){
      arr[i] = in.next().charAt(0);
    }
    dfs(0);	//核心算法
  }
  private static void dfs(int step){//前step个字符已排列，正在排列第step个字符
    if(step == box.length) {//当全部字符排列完毕，输出并return
      printf(box);
      return;
    }
    for(int i = 0; i < box.length; i++){
      if(flag[i]==true) continue;//第i个字符已使用则跳出
      box[step] = arr[i];//将第i个字符放入第step个盒子
      flag[i] = true;//标记第i个字符已使用
      dfs(step+1);
      flag[i] = false;//标记第i个字符未使用
    }
  }
  private static void printf(char[] flag){
    for(int i = 0; i < flag.length; i++){
      System.out.print(flag[i]+" ");
    }
    System.out.println("");
  }
}

走迷宫

现有一个n*m的迷宫，标记从起点(startx,starty)到终点(endx,endy)的一条路径
例如，0为可行，1为墙壁，2为走过的路径标记，起点为(0,0)，终点为(3,3)

1
2
3
4
0 1 0 1
0 0 0 1
0 0 0 0
1 0 0 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
public class Main{
  
  public static void main(String[] args) throws Exception {
    Scanner in = new Scanner(System.in);
    int n = in.nextInt();
    int m = in.nextInt();
    int startx = in.nextInt();
    int starty = in.nextInt();
    int endx = in.nextInt();
    int endy = in.nextInt();
    int[][] maze = new int[n+1][m+1];
    for(int i = 1; i <= n; i++){
      for(int j = 1; j <= m; j++){
        maze[i][j] = in.nextInt();
      }
    }
    maze[startx][starty] = 2;
    dfs(startx,starty,endx,endy,maze);
  }
  
  private static void dfs(int startx, int starty, int endx, int endy, int[][] maze) {
    if(startx==endx&&starty==endy){
      printf(maze);
      return;
    }
    
    if(startx-1 >= 1 && maze[startx-1][starty]==0){//往上走
      maze[startx-1][starty]=2;
      dfs(startx-1,starty,endx,endy,maze);
      maze[startx-1][starty] = 0;
    }
    
    if(startx+1 <= maze.length-1 && maze[startx+1][starty]==0){//往下走
      maze[startx+1][starty]=2;
      dfs(startx+1,starty,endx,endy,maze);
      maze[startx+1][starty]=0;
    }
    
    if(starty-1 >= 1 && maze[startx][starty-1]==0){//往左走
      maze[startx][starty-1]=2;
      dfs(startx,starty-1,endx,endy,maze);
      maze[startx][starty-1]=0;
    }
    
    if(starty+1 <= maze[startx].length-1 && maze[startx][starty+1]==0){//往右走
      maze[startx][starty+1]=2;
      dfs(startx,starty+1,endx,endy,maze);
      maze[startx][starty+1]=0;
    }
  }

  private static void printf(int[][] arr){
    for(int i = 0; i < arr.length; i++){
      for(int j = 0; j < arr[i].length; j++){
        System.out.print(arr[i][j]+" ");
      }
      System.out.println("");
    }
  }
}

广搜

走迷宫之最短路径

现有一个n*m的迷宫，输出从起点(startx,starty)到终点(endx,endy)的最短路径步数
例如，0为可行，*为墙壁，起点为(0,0)，终点为(3,3)

1
2
3
4
0 1 0 1
0 0 0 1
0 0 0 0
1 0 0 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
public class Main{
  public static void main(String[] args) throws Exception {
    Scanner in = new Scanner(System.in);
    int n = in.nextInt();
    int m = in.nextInt();
    int startX = in.nextInt();
    int startY = in.nextInt();
    int endX = in.nextInt();
    int endY = in.nextInt();
    char[][] maze = new char[n+1][m+1];
    for(int i = 1; i <= n; i++){
      for(int j = 1; j <= m; j++){
        maze[i][j] = in.next().charAt(0);
      }
    }
    
    int[] queueX = new int[n*n];//x坐标队列
    int[] queueY = new int[n*n];//y坐标队列
    int head = 0;//头指针
    int tail = 1;//尾指针
    queueX[head] = startX;//起点入队
    queueY[head] = startY;
    maze[queueX[head]][queueY[head]] = (char)('a');
    
    while(tail-head>0){//判断队列不为空
      int x = queueX[head];
      int y = queueY[head];
      printf(maze);
      if(x==endX && y==endY){//到达终点
        System.out.println(maze[endX][endY]-'a');
        break;
      }
      if(x-1>=1 && maze[x-1][y]=='0'){//往左走
        maze[x-1][y] = (char) (maze[x][y]+1);
        queueX[tail] = x-1;//入队
        queueY[tail] = y;
        tail++;
      }
      if(x+1<=maze.length-1 && maze[x+1][y]=='0'){//往右走
        maze[x+1][y] = (char) (maze[x][y]+1);
        queueX[tail] = x+1;//入队
        queueY[tail] = y;
        tail++;
      }
      if(y-1>=1 && maze[x][y-1]=='0'){//往上走
        maze[x][y-1] = (char) (maze[x][y]+1);
        queueX[tail] = x;//入队
        queueY[tail] = y-1;
        tail++;
      }
      
      if(y+1<=maze[x].length-1 && maze[x][y+1]=='0'){//往下走
        System.out.println((y+1)+","+maze[x].length+","+maze[x][y+1]);
        maze[x][y+1] = (char) (maze[x][y]+1);
        queueX[tail] = x;//入队
        queueY[tail] = y+1;
        tail++;
      }
      head++;//出队
    }
    
  }

  private static void printf(char[][] maze){
    for(int i = 1; i < maze.length; i++){
      for(int j = 1; j < maze[i].length; j++){
        System.out.print(maze[i][j]+" ");
      }
      System.out.println("");
    }
    System.out.println("");
  }
}