回溯法

[Ir1d]

https://oi-wiki.cf/search/backtracking/

[Yerosius]

如果对回溯难以理解，说明对递归没有真正理解，出现了知识上的递归。不要对递归感到恐惧，应将递归视做处理问题规模无关和自相似性，能极大程度减少编码量的工具，而不是视为累赘和负担。如果实在难以理解，建议先复习高中的数学归纳法，并善用VS、CLion等IDE的并行堆栈、并行监视功能，它们都是帮助理解递归和回溯的优秀工具。加油。

[zhangjialin996]

迷宫问题java

[zhangjialin996]

dfs

import java.util.*;

public class P1605 {
  static int N;
  static int M;
  static int T;
  static int[][] map; // 1 障碍 0 可行
  static boolean[][] visited;
  static int planNum = 0;
  static int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
  static int res;

  public static void main(String... args){
    Scanner in = new Scanner(System.in);
    N = in.nextInt();
    M = in.nextInt();
    T = in.nextInt();
    map = new int[N][M];
    visited = new boolean[N][M];

    int SX = in.nextInt() - 1;
    int SY = in.nextInt() - 1;
    int FX = in.nextInt() - 1;
    int FY = in.nextInt() - 1;

    for(int i = 0; i < T; i++){
      int xB = in.nextInt() - 1;
      int yB = in.nextInt() - 1;
      map[xB][yB] = 1;
    }

    // map[SX][SY] = 1;
    // queue.offer(new int[]{SX, SY});
    dfs(SX, SY, FX, FY);

    System.out.println(res);
    in.close();
  }

  public static void dfs(int curX, int curY, int FX, int FY){
    if(curX == FX && curY == FY) {
      res++;
      return ;
    }
    visited[curX][curY] = true;
    for(int[] direction : directions){
      if( ifLand(curX + direction[0], curY + direction[1]) && !visited[curX + direction[0]][curY + direction[1]]){ 
        // 是陆地
        dfs(curX + direction[0], curY + direction[1], FX, FY);
      }
    }
    visited[curX][curY] = false;
  }

  // 判断坐标是否是陆地，而不是超出边界或者是地图
  public static boolean ifLand(int curX, int curY){
    if(curX < 0 || curX >= N) return false;
    if(curY < 0 || curY >= M) return false;
    if(map[curX][curY] != 0) return false;
    return true;
  }
}

[zhangjialin996]

这个N皇后问题写的是真优雅

[zhangjialin996]

N皇后java
每次都会判断当前是否满足行列对角斜对角是否有两个及以上的queen出现，出现则返回
这一版对付N <= 10的情况还行，但是12 、13会严重超时

import java.util.*;

public class P1291 {
  static int N;
  static List<int[]> res = new ArrayList<>();
  static boolean[][] chose;

  public static void main(String... args){
    Scanner in = new Scanner(System.in);
    N = in.nextInt();
    chose = new boolean[N][N];
    dfs(0);
    
    for(int i = 0; i < Math.min(3, res.size()); i++){
      int[] oneS = res.get(i);
      for(int j = 0; j < N; j++){
        System.out.print(oneS[j] + " ");
      }
      System.out.println();
    }
    System.out.println(res.size());
  }

  public static void dfs(int column){
    if(!checkIfSatisfy(chose)) return ;
    if(column == N){
      int[] oneSolution = new int[N];
      int index = 0;
      for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
          if(chose[i][j]) oneSolution[index++] = j + 1;
        }
      }
      res.add(oneSolution);
      return ;
    }
    for(int i = 0; i < N; i++){
      chose[column][i] = true;
      dfs(column + 1);
      chose[column][i] = false;
    }
  }

  public static boolean checkIfSatisfy(boolean[][] curTable){
    // row column
    for(int i = 0; i < N; i++){
      int rowSum = 0;
      int colSum = 0;
      for(int j = 0; j < N;j++){
        if(curTable[i][j]) rowSum++;
        if(curTable[j][i]) colSum++;

        // 访问当前结点对角线
        int sumLineOne = getLineOne(curTable, i, j);
        int sumLineTwo = getLineTwo(curTable, i, j);
        if(sumLineOne > 1 || sumLineTwo > 1) return false;
      }
      if(colSum > 1 || rowSum > 1) return false;
    }

    for(int i = 0; i < N; i++){
      int sum = 0;
      for(int j = 0; j < N;j++){
        if(curTable[i][j]) sum++;
      }
      if(sum > 1) return false;
    }

    return true;
  }

  public static int getLineOne(boolean[][] curTable, int i, int j){
    int sum = 0;
    if(i != 0 && j != 0){
      while(true){
        i--;
        j--;
        if(i==0 || j == 0) break;
      }
    }
    for(;i < N && j < N; i++,j++){
      if(curTable[i][j]) sum++;
    }
    return sum;
  }

  public static int getLineTwo(boolean[][] curTable, int i, int j){
    int sum = 0;
    if(i != 0 && j != N - 1){
      while(true){
        i--;
        j++;
        if(i==0 || j == N - 1) break;
      }
    }
    for(;i < N && j < N && i >= 0&& j >= 0; i++,j--){
      if(curTable[i][j]) sum++;
    }
    return sum;
  }
}

[zhangjialin996]

简化写法
关于check[3][2 * N + 1]：

• check[0]存储每一列的占位情况
• check[1]存储每一对角线的占位情况，同一主对角线上的任意两个元素满足x1 + y1 = x2 + y2
• check[2]存储每一斜对角线的占位情况，同一斜对角线上的任意两个元素满足N - x1 + y1 = N - x2 + y2

长度为2 * N+ 1是因为对于一个N*N的正方形，有2 * N + 1条对角线

import java.util.*;

public class P1291 {
  static int N;
  static int[] res;
  static boolean[][] check;
  static int Num = 0;
  static int printTimes = 0;

  public static void main(String... args){
    Scanner in = new Scanner(System.in);
    N = in.nextInt();
    res = new int[N];
    check = new boolean[3][N * 2 + 1]; // 0 列 1 主对角 2 斜对角
    dfs(0);
    System.out.println(Num);
  }

  public static void dfs(int line){
    if(line == N){
      Num++;
      if(printTimes < 3){
        for(int i = 0; i < N; i++){
          System.out.print(res[i] + " ");
        }
        System.out.println();
        printTimes++;
      }
      return ;
    }
    for(int i = 0; i < N; i++){
      if(!check[0][i] && !check[1][i + line] && !check[2][N - line + i]){
        res[line] = i + 1;
        check[0][i] = true;
        check[1][i + line] = true;
        check[2][N - line + i] = true;
        dfs(line + 1);
        // recur
        check[0][i] = false;
        check[1][i + line] = false;
        check[2][N - line + i] = false;
      }
    }
  }
}

[purinliang]

我觉得给迷宫这道题用BFS首先就很迷惑，既然跟最短路无关，而且要求对独立的路径进行计数，这题当然是天生用DFS去做的。这道题用BFS+回溯算法实在是太抽象了，可以称得上是为了这碟醋，包了一顿饺子。有没有大佬可以提供一个看起来BFS相对于DFS有明显优势或者BFS和DFS相当的、需要使用回溯技巧的例子？我目前理解回溯算法几乎是和DFS强绑定的，希望能找到一个实用的BFS回溯的例子。