首页 > 代码库 > 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游戏 搜索
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。