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