文章

路径之谜(2016国赛)

路径之谜1.png路径之谜2.png

深度优先搜素

#include<bits/stdc++.h>
using namespace std;
long long int cnt=0,flag=0,n;
long long int a[100];
long long int b[100];
long long int dist[1001];
long long int mo1[4]={0,1,-1,0};
long long int mo2[4]={1,0,0,-1};
long long int dp[1001][1001];
long long int  check(){
    long long int i;
    for(i=0;i<n;i++){
        if(a[i]==b[i]&&a[i]==0){
            
        }else return 0;
    }
    return 1;
}
void dfs(long long int x,long long int y){
    if(x==n-1&&y==n-1) {
        if(check()==1){
            flag=1;
        }else {
            cnt--;
            dp[x][y]=0;
            a[x]++;
            b[y]++;
        }
        return ;
    }
    long long int tx,ty,i;
    for(i=0;i<4&&flag==0;i++){
        tx=x+mo1[i];
        ty=y+mo2[i];
        if(tx>=0&&tx<n&&ty>=0&&ty<n&&dp[tx][ty]==0&&a[tx]-1>=0&&b[ty]-1>=0){
            //不超出边界 没有走过 符合条件 
            a[tx]--;
            b[ty]--;
            dp[tx][ty]=1;
            dist[cnt]=tx*n+ty;
            cnt++;
            dfs(tx,ty);
        }
    }
    if(flag==0){
        cnt--;
        dp[x][y]=0;
        a[x]++;
        b[y]++;
    }
    
    return ;
}
int main()
{
    long long int i;
    cin>>n;
    for(i=0;i<n;i++) cin>>b[i];
    for(i=0;i<n;i++) cin>>a[i];
    a[0]--;
    b[0]--;
    dp[0][0]=1;
    dist[0]=0;
    cnt++;
    dfs(0,0);
    for(i=0;i<cnt;i++){
        cout<<dist[i]<<' ';
    }cout<<endl;
    return 0;
}

原题链接

https://www.lanqiao.cn/problems/89/learning/

License:  CC BY 4.0