蓝桥杯真题——路径之谜，DFS深搜

题目链接: https://www.lanqiao.cn/problems/89/learning/

AC代码如下:

#include <iostream>
#include <queue>
using namespace std;

const int N = 25;


//colP北墙，rowP西墙靶子数
int colP[N],rowP[N];
//state数组，存储状态（哪个格子已经被走过了）
int dst[N][N];
//x,y四个方向的偏移量
int ox[4]={0,0,-1,1},oy[4]={1,-1,0,0};
//双端队列
deque<int> path;

int n;


//检查靶子是否为空
bool checkComp(){
    for(int i=0;i<n;i++) {
        if(colP[i]!=0||rowP[i]!=0) return false;
    }
    return true;
}

//检查是否越界
bool check(int x,int y){
    return x>=0&&x<n&&y>=0&&y<n;
}

void dfs(int x,int y){
    //看下方解释
   //    if(rowP[x]==0||colP[y]==0) {
    //    return;
    //}
    //扣除靶子上的箭矢
    rowP[x] --,colP[y]--;
    //将当前格子标记为已走过
    dst[x][y] = 1;
    //在队尾存储当前格子 （输出的格子编号为n*x+y）
    path.push_back(n*x+y);

    //如果已经走到了终点格，判断靶子数是否为空
    //为空则输出正确路径
    if(x==n-1&&y==n-1&&checkComp()){
        while (!path.empty()) {
            printf("%d", path.front());
            path.pop_front();
            printf(path.empty() ? "\n" : " ");
        }
        //只取一条路径即可，直接exit进程
        exit(0);
    }
    //枚举上下左右四个偏移量，依次走过去
    for(int i=0;i<4;i++){
        int nx = x+ox[i],ny=y+oy[i];
        //检查边界，靶子箭矢数是否已空
        if(check(nx,ny)&&!dst[nx][ny]&&
		rowP[nx]>0&&colP[ny]>0){
            //走过去
            dfs(nx,ny);
            //如果上面的dfs没有走到头，则需要回溯状态，从i+1开始继续尝试
            path.pop_back();
            dst[nx][ny] = 0;
            ++rowP[nx],++colP[ny];
        }
    }
}


int main(){
    cin>>n;
    for(int i=0;i<n;i++) cin>>colP[i];
    for(int i=0;i<n;i++) cin>>rowP[i];
    dfs(0,0);
    return 0;
}

我以为做DFS题时最该优先考虑的是递归的顺序，如果没有经过重复思考边界条件就开始动手，debug的过程中会因为理不清递归层得抑郁症。为了防止这种情况，考虑的时候任何一个细节都不应该放过，像上面这道题
如果我们将这段判断靶子箭矢是否为空的代码放在函数入口处

if(rowP[x]==0||colP[y]==0) {
    return;
}

而不在枚举四个方向时判断靶子数量再进行dfs，那么回溯回来时，我们进行了一次不必要的

++rowP,++colP

这会影响最后的结果，回溯的时候每个状态都很重要，稍加不慎会做到缺漏或影响正确结果

这周打算多刷点DFS题，周日会整理到网站上