luogu 8642 路径之谜（回溯法）

原题#

https://www.luogu.com.cn/problem/P8642

题解#

回溯法七步归纳#

确定状态 state （第一步）#

由于每个格子只能访问一次，所以需要设定一个 bool 数组 vis 用于表示访问状态：

vector<vector<bool>> vis(n, vector<bool>(n, false));

需要输出路径，所以需要开一个 path 数组，输出路径：

vector<int> path;

行列数组int row[]和int col[]，对应剩余行列可走的格子
以及当前位置坐标 x 与 y

一般用 dfs 做回溯函数，然后将基础变量 x与y作为回溯参数，即dfs(x, y)，然后剩余变量作为全局上下文

确定非法状态（第二步）#

if(x < 0 || x >= n || y < 0 || y >= n)return false;
if(vis[x][y]) return false;
if(row[x] == 0 || col[y]== 0)return false;

更新状态（第三步）#

row[x] --;
col[y] --;
vis[x][y] = true;
path.push_back(x * n + y);

结束状态（第四步）#

if (
  x == n-1 && y == n - 1 &&  // 当前在右下角
  accumulate(row, row + n, 0) == 0 && // 行列格子数量满足
  accumulate(col, col + n, 0) == 0
) 
  return true;

状态转移（枚举下一个状态，第五步）#

当前格子需要往下一个状态转移，只有上下左右四种移动方式

int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

然后开始递归

for(int d = 0; d < 4; d ++){
  if (dfs(x + dx[d], y + dy[d])) return true;
}

假设找到路径，就返回

状态还原（与状态更新相反，第六步）#

row[x] ++;
col[y] ++;
vis[x][y] = false;
path.pop_back();
return false;  // 此路不通

调用#

传入初始状态，并返回数组，就能找到路径

dfs[0][0];
return path;

优化与状态剪枝（精髓，第七步）#

如果某状态的后续状态一定不合法，就剪枝。去掉即可。（需要总结规律）

// 放在状态更新前，即某一行即将变为 0 而之前的行和还不为 0 则 false
if (row[x] == 1 && accumulate(row, row + x, 0) != 0) return false; 
if (col[y] == 1 && accumulate(col, col + y, 0) != 0) return false;

总代码#

注意，不同代码，可能步骤顺序不同，需要根据实际变通

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 30;
vector<vector<bool>> vis(MAXN, vector<bool>(MAXN, false));
vector<int> path;
int row[MAXN], col[MAXN];
int n;
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

bool dfs(int x, int y){
    
    // step 2
    if(x < 0 || x >= n || y < 0 || y >= n) return false;
    if(vis[x][y]) return false;
    if(row[x] == 0 || col[y]== 0) return false;
    
    // step 7
    if (row[x] == 1 && accumulate(row, row + x, 0) != 0) return false; 
    if (col[y] == 1 && accumulate(col, col + y, 0) != 0) return false;
    
    // step 3
    row[x] --;
    col[y] --;
    vis[x][y] = true;
    path.push_back(x * n + y);
    
    // step 4
    if (
      x == n-1 && y == n - 1 &&  // 当前在右下角
      accumulate(row, row + n, 0) == 0 && // 行列格子数量满足
      accumulate(col, col + n, 0) == 0
    ) 
      return true;
    
    // step 5
    for(int d = 0; d < 4; d ++){
      if (dfs(x + dx[d], y + dy[d])) return true;
    }
    
    // step 6
    row[x] ++;
    col[y] ++;
    vis[x][y] = false;
    path.pop_back();
    return false; 
}

int main(){
    cin >> n;
    for(int i = 0; i < n; i ++)
        cin >> col[i];
    for(int i = 0; i < n; i ++)
        cin >> row[i];
        
    dfs(0, 0);
    for(int i = 0; i < path.size(); i ++){
        cout << path[i] << " ";
    }
    return 0;
}