路径之谜
思路
前置知识:深度搜索模板 搜索所有可以找的路径,将走过的靶子减去一 走到最后一个格子的时候,直接去判断所有的靶子 只有除最后一个位置的靶子,其余靶子都归零的时候,判断一个最后一个位置横坐标和纵坐标的靶子 如果这两个靶子都是1
,是我们要的答案,输出路径 每次走过一个格子,都将对应的坐标存入一个path
数组中,回溯时就将他复原回去 对于其他状态也需要进行复原,美名其曰-恢复现场
Coding
# include <iostream>
# include <vector>
using namespace std;
const int N = 21 ;
int vx[ ] = { 0 , 0 , 1 , - 1 } ;
int vy[ ] = { 1 , - 1 , 0 , 0 } ;
int xba[ N] ;
int yba[ N] ;
int path[ N* N] ;
int n, idx;
bool st[ N] [ N] ;
inline void dfs ( int x, int y) {
if ( x == n- 1 && y == n- 1 ) {
for ( int i = 0 ; i < n- 1 ; i++ ) {
if ( xba[ i] || yba[ i] ) return ;
}
if ( xba[ n- 1 ] == 1 && yba[ n- 1 ] == 1 ) {
path[ idx ++ ] = n* y+ x;
for ( int j = 0 ; j < idx; j++ ) {
cout << path[ j] << ' ' ;
} cout << endl;
}
}
for ( int i = 0 ; i < 4 ; i++ ) {
int nx, ny;
nx = x + vx[ i] , ny = y + vy[ i] ;
if ( x >= 0 && y >= 0 && x < n && y < n && ! st[ x] [ y] ) {
st[ x] [ y] = true;
xba[ x] -- ;
yba[ y] -- ;
path[ idx ++ ] = n* y+ x;
dfs ( nx, ny) ;
xba[ x] ++ ;
yba[ y] ++ ;
idx-- ;
st[ x] [ y] = false;
}
}
}
int main ( ) {
cin >> n;
for ( int i = 0 ; i < n; i++ ) {
cin >> xba[ i] ;
}
for ( int i = 0 ; i < n; i++ ) {
cin >> yba[ i] ;
}
dfs ( 0 , 0 ) ;
}