2048
user_1164828
c_cpp
15 days ago
3.6 kB
2
Indexable
Never
//2048 #include<stdio.h> int n,max; void swipeL(int arr[][4]){ for(int i=0;i<4;i++){ int x=0,x2=1; while(x<4&&x2<4){ if(arr[i][x]==0){ x++; x2++; } else if(arr[i][x2]==0) x2++; else if(arr[i][x2]!=arr[i][x]){ x=x2; x2++; } else{ arr[i][x]*=2; arr[i][x2]=0; x=x2+1; x2=x2+2; } } int index=0; for(int j=0;j<4;j++) if(arr[i][j]!=0){ arr[i][index++]=arr[i][j]; if(j!=index-1) arr[i][j]=0; } } } void swipeR(int arr[][4]){ for(int i=0;i<4;i++){ int x=3,x2=2; while(x>=0&&x2>=0){ if(arr[i][x]==0){ x--; x2--; } else if(arr[i][x2]==0) x2--; else if(arr[i][x2]!=arr[i][x]){ x=x2; x2--; } else{ arr[i][x]*=2; arr[i][x2]=0; x=x2-1; x2-=2; } } int index=3; for(int j=3;j>=0;j--) if(arr[i][j]!=0){ arr[i][index--]=arr[i][j]; if(j!=index+1) arr[i][j]=0; } } } void swipeT(int arr[][4]){ for(int i=0;i<4;i++){ int x=0,x2=1; while(x<4&&x2<4){ if(arr[x][i]==0){ x++; x2++; } else if(arr[x2][i]==0) x2++; else if(arr[x2][i]!=arr[x][i]){ x=x2; x2++; } else{ arr[x][i]*=2; arr[x2][i]=0; x=x2+1; x2+=2; } } int index=0; for(int j=0;j<4;j++) if(arr[j][i]!=0){ arr[index++][i]=arr[j][i]; if(j!=index-1) arr[j][i]=0; } } } void swipeB(int arr[][4]){ for(int i=0;i<4;i++){ int x=3,x2=2; while(x>=0&&x2>=0){ if(arr[x][i]==0){ x--; x2--; } else if(arr[x2][i]==0) x2--; else if(arr[x2][i]!=arr[x][i]){ x=x2; x2--; } else{ arr[x][i]*=2; arr[x2][i]=0; x=x2-1; x2-=2; } } int index=3; for(int j=3;j>=0;j--) if(arr[j][i]!=0){ arr[index--][i]=arr[j][i]; if(j!=index+1) arr[j][i]=0; } } } bool check(int arr[][4]){ for(int i=0;i<16;i++){ int r=i/4; int c=i%4; if(arr[r][c]!=0){ for(int j=i+1;j<16;j++){ int r2=j/4; int c2=j%4; if(arr[r2][c2]==arr[r][c]) return false; } } } return true; } bool backTrack(int k,int arr[][4],int h){ int bk[4][4]; for(int i=0;i<4;i++) for(int j=0;j<4;j++) bk[i][j]=arr[i][j]; if(h==0); else if(h==1) swipeL(bk); else if(h==2) swipeR(bk); else if(h==3) swipeT(bk); else swipeB(bk); bool c=true; for(int i=0;i<4;i++) for(int j=0;j<4;j++) if(arr[i][j]!=bk[i][j]){ c=false; break; } if(c&&h!=0) return false; if(k==n){ int m=0; for(int i=0;i<4;i++) for(int j=0;j<4;j++) if(bk[i][j]>max) max=bk[i][j]; if(check(bk)) return true; return false; } if(backTrack(k+1,bk,1)) return true; if(backTrack(k+1,bk,2)) return true; if(backTrack(k+1,bk,3)) return true; if(backTrack(k+1,bk,4)) return true; return false; } int main(){ // clock_t start,end; // start=clock(); freopen("Text.txt","r",stdin); int test; int arr[4][4]; scanf("%d",&test); for(int t=1;t<=test;t++){ scanf("%d",&n); for(int i=0;i<4;i++) for(int j=0;j<4;j++) scanf("%d",&arr[i][j]); max=0; backTrack(0,arr,0); printf("#%d %d\n",t,max); } // end=clock(); // printf("%d",end-start); return 0; }
Leave a Comment