2048

 avatar
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