Luogu 8642 Path Mystery (Backtracking Method)

Original Problem#

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

Problem Solution#

Backtracking Method Seven Steps Summary#

Determine State (Step One)#

Since each cell can only be accessed once, a bool array vis is needed to represent the access state:

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

A path array is needed to output the path:

vector<int> path;

Row and column arrays int row[] and int col[], corresponding to the remaining accessible cells in rows and columns, as well as the current position coordinates x and y.

Generally, use dfs to create the backtracking function, and use the basic variables x and y as backtracking parameters, i.e., dfs(x, y), while the remaining variables are treated as global context.

Determine Invalid States (Step Two)#

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;

Update State (Step Three)#

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

End State (Step Four)#

if (
  x == n-1 && y == n - 1 &&  // Currently at the bottom right corner
  accumulate(row, row + n, 0) == 0 && // The number of accessible cells in rows and columns meets the requirement
  accumulate(col, col + n, 0) == 0
) 
  return true;

State Transition (Enumerate Next State, Step Five)#

The current cell needs to transition to the next state, with only four possible movement directions: up, down, left, right.

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

Then start recursion.

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

Assuming a path is found, return.

State Restoration (Opposite of State Update, Step Six)#

row[x] ++;
col[y] ++;
vis[x][y] = false;
path.pop_back();
return false;  // This path is blocked

Invocation#

Pass in the initial state and return the array to find the path.

dfs[0][0];
return path;

Optimization and State Pruning (Essence, Step Seven)#

If a certain state's subsequent states are definitely invalid, prune it. Just remove it. (Need to summarize the rules.)

// Place this before state update, i.e., if a certain row is about to become 0 while the previous rows are not 0, then return 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;

Complete Code#

Note that different codes may have different step orders, and adjustments should be made according to the actual situation.

#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 &&  // Currently at the bottom right corner
      accumulate(row, row + n, 0) == 0 && // The number of accessible cells in rows and columns meets the requirement
      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;
}