[蓝桥杯2016决赛]路径之谜

叁歲伎倆 2023-10-04 10:49 18阅读 0赞

#include <iostream>
    #include <algorithm>
    #include <cstring>
    #include <queue>
    #include <set>
    #include <math.h>
    #include <map>
    using namespace std;
    typedef long long LL;
    const int N=25;
     
    int r[N],l[N];
    int n;
    int dx[]={
        0,0,-1,1},dy[]={
        1,-1,0,0};
    int path[N*N];
    int t;
    bool st[N][N];
     
    bool check()
    {
        
         for(int i=0;i<n;i++)
              if(r[i]!=0||l[i]!=0) return false;
         return true;
    }
    bool dfs(int a,int b)
    {
        
         if(a==n-1&&b==n-1)
         {
        
              if(check())
              {
        
                   for(int i=0;i<t;i++)
                   {
        
                        cout<<path[i];
                        if(i!=t-1) cout<<' ';
                   }
                   cout<<endl;
                   return true;
              }
              return false;
         }
         for(int i=0;i<4;i++)
         {
        
              int x=dx[i]+a,y=dy[i]+b;
              if(x>=0&&x<n&&y>=0&&y<n&!st[x][y])
              {
        
                   if(r[y]>0&&l[x]>0)
                   {
        
                        st[x][y]=true;
                        r[y]--,l[x]--;
                        path[t]=x*n+y;
                        t++;
     
                        if(dfs(x,y)) return true;
     
                        st[x][y]=false;
                        r[y]++,l[x]++;
                        t--;
                   }
              }
         }
         return false;
    }
    int main()
    {
        
         cin>>n;
         for(int i=0;i<n;i++) cin>>r[i];
         for(int i=0;i<n;i++) cin>>l[i];
         r[0]--,l[0]--;
         path[0]=0;
         st[0][0]=true;
         t++;
         dfs(0,0);
     
         return 0;
    }