蓝桥杯2016年第七届真题-路径之谜 简单的dfs

解题思路:

注意事项:

参考代码:

#include"bits/stdc++.h"
using namespace std;
#define ll long long
ll n,p[25][25],k,ppp;
vector<ll> v;
ll dx[]={0,0,1,-1};
ll dy[]={1,-1,0,0};
bool vis[25][25];
void dfs(ll x,ll y){
    if(ppp)return;
    if(x==n&&y==n){
        for(ll i=1;i<=n;i++){
            if(p[0][i]!=0||p[i][0]!=0)return;
        }
        for(ll i=0;i<v.size();i++){
            cout<<v[i]<<" ";
        }
        ppp=1;
        return;
    }
    for(ll i=0;i<4;i++){
        ll xx=x+dx[i];
        ll yy=y+dy[i];
        if(xx<1||xx>n||yy<1||yy>n||vis[xx][yy]||p[xx][0]<=0||p[0][yy]<=0)continue;
        vis[xx][yy]=true;
        v.push_back(p[xx][yy]);
        p[0][yy]--;
        p[xx][0]--;
        dfs(xx,yy);
        v.erase(v.end()-1);
        vis[xx][yy]=false;
        p[0][yy]++;
        p[xx][0]++;
    }
}
int main(){
    cin>>n;
    for(ll i=1;i<=n;i++){
        for(ll j=1;j<=n;j++){
            p[i][j]=k++;
        }
    }
    for(ll i=1;i<=n;i++)cin>>p[0][i];
    for(ll i=1;i<=n;i++)cin>>p[i][0];
    vis[1][1]=true;
    v.push_back(p[1][1]);
    p[1][0]--;
    p[0][1]--;
    dfs(1,1);
    return 0;
}