首页 > 代码库 > NOIp 2011 mayan游戏 搜索

NOIp 2011 mayan游戏 搜索

 

搜索。

因为要求字典序最小 所以都右移 除非那个方格为空。

代码如下:

 1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<cstdlib> 5 #define For(i,x,y) for(int i=x;i<=y;++i) 6 using namespace std; 7 int a[10][10]; 8 int cnt[10];int n;    int ncnt[10]; 9 int qx[10],qy[10],qg[10];10 inline bool check()11 {12     int v[10][10];memset(v,0,sizeof(v));13     memset(ncnt,0,sizeof(ncnt));14     For(i,0,4)15     {16         For(j,0,6)17         {18             if(a[i][j])a[i][ncnt[i]++]=a[i][j];19         }20         For(j,ncnt[i],6)a[i][j]=0;21     }22     bool flag=false;23     For(i,0,4)24     {25         For(j,0,6)26         {27             if(!a[i][j])continue;28             int k=0;int u=a[i][j];29             for(k=j+1;a[i][k]==u;++k);30             if(k-j>=3){flag=1;For(p,j,k-1)v[i][p]=1;}31             for(k=i+1;a[k][j]==u;++k);32             if(k-i>=3){flag=1;For(p,i,k-1)v[p][j]=1;}33         }34     }35     if(flag)For(i,0,4)For(j,0,6)if(v[i][j]==1)a[i][j]=0;36     For(i,0,4)cnt[i]=ncnt[i];37     return flag;38 }39 inline bool done()40 {41     For(i,0,4)For(j,0,6)if(a[i][j])return 0;return 1;42 }43 void dfs(int step)44 {45     int tmp[10][10],tcnt[10];46     while(check());47     if(done())48     {49         For(i,1,step-1)50             printf("%d %d %d\n",qx[i],qy[i],qg[i]);51         exit(0);52     }53     if(step==n+1)return;54     For(i,0,4)For(j,0,6)tmp[i][j]=a[i][j];55     For(i,0,4)tcnt[i]=cnt[i];    56     For(i,0,4)57     {58         For(j,0,cnt[i])59         {60             if(i!=4&&a[i][j]!=a[i+1][j]&&a[i][j])61             {62                 swap(a[i][j],a[i+1][j]);qx[step]=i;qy[step]=j;qg[step]=1; 63                 dfs(step+1);64                 For(i,0,4)For(j,0,6)a[i][j]=tmp[i][j];65                 For(i,0,4)cnt[i]=tcnt[i];66             }67             if(i!=0&&!a[i-1][j])68             {69                 swap(a[i-1][j],a[i][j]);70                 qx[step]=i;qy[step]=j;qg[step]=-1; 71                 dfs(step+1);72                 swap(a[i-1][j],a[i][j]);73                 For(i,0,4)For(j,0,6)a[i][j]=tmp[i][j];74                 For(i,0,4)cnt[i]=tcnt[i];75             }76         }77     }78 }79 int main()80 {81     cin>>n;82     For(i,0,4)83     {84         int x;cin>>x;85         while(x)86         {87             a[i][cnt[i]++]=x;88             cin>>x;89         }90     }91     dfs(1);92     cout<<-1;93 }

 

NOIp 2011 mayan游戏 搜索