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;
}