Untitled
unknown
plain_text
2 years ago
16 kB
3
Indexable
2048
Game 2048 is set up on a board 4x4, include random number 0 and M with M = 2^n (0<=n<=11).
You can arrange the array in horizontal or vertical directions. In each arrangement, all rows or columns will be stacked in the corresponding direction. During arrangement, two adjacent numbers with the same value will be added up to make a number.
For examples:
After K times of moving (2<=K<=11), find and print on the screen the largest number in the array which you create.
Input
1 //The number of test case
3 //K: The number of moves (arrangement)
0 2 2 0
4 0 0 0
0 0 8 0
2 2 4 0
Output:
#1 16
50
3
0 2 2 0
4 0 0 0
0 0 8 0
2 2 4 0
2
0 2 2 0
4 0 0 0
0 0 8 0
2 2 4 0
4
0 2 2 0
4 0 0 0
0 0 8 0
2 2 4 8
3
2 2 2 2
4 4 4 4
8 8 8 8
16 16 16 16
4
2 0 0 0
0 4 0 0
0 8 0 0
0 0 0 2
7
2 0 0 0
0 4 0 0
0 8 0 0
0 0 0 2
6
0 4 2 0
4 0 0 0
0 0 8 2
2 2 4 8
4
8 2 2 2
4 2 4 8
16 8 2 2
2 4 8 4
9
8 2 2 2
4 2 4 8
16 8 2 2
2 4 8 4
11
8 4 16 2
4 8 4 8
16 8 2 2
2 4 8 4
9
4 0 32 64
4 64 0 4
8 4 16 4
32 2 0 0
8
8 0 2 16
0 64 16 2
32 16 4 2
2 0 4 2
9
2 4 2 4
2 64 32 8
32 2 64 16
8 4 32 0
10
4 8 2 32
32 32 2 32
0 0 32 4
4 16 4 64
10
32 16 16 0
0 32 0 8
64 2 64 4
2 16 4 64
10
8 64 32 16
8 8 4 32
2 2 8 16
0 64 16 64
10
64 8 8 8
8 2 32 64
2 64 16 2
8 32 32 16
9
16 0 2 2
32 16 16 8
4 32 2 8
16 0 0 0
11
64 0 0 32
32 32 64 4
4 32 16 8
0 8 4 64
11
8 4 16 32
8 2 4 2
0 8 2 0
0 64 4 4
8
64 32 4 32
0 4 16 2
8 32 0 8
16 32 2 0
8
16 4 64 2
16 8 0 16
32 8 4 64
0 0 0 4
9
4 8 8 64
32 64 0 4
2 8 0 0
4 16 8 2
8
16 0 16 8
2 8 16 8
64 32 0 2
32 8 16 16
10
8 0 4 64
0 2 2 64
4 0 0 8
16 2 0 16
9
64 64 8 32
64 32 16 64
4 32 4 16
16 8 4 0
10
8 2 4 64
16 64 8 2
0 0 16 16
64 8 4 16
10
16 16 8 8
0 0 2 8
2 0 0 32
0 8 32 8
8
4 4 4 4
16 0 64 16
0 0 8 0
32 16 0 2
11
8 0 2 16
64 2 2 2
8 32 0 4
8 2 0 4
9
4 4 2 64
4 16 32 64
4 32 0 0
64 2 16 32
10
16 4 2 2
16 4 2 8
64 16 16 0
16 32 2 0
8
0 32 2 0
0 0 16 8
4 4 0 2
64 2 16 0
8
32 64 2 64
4 16 16 8
2 2 8 2
0 16 64 32
8
64 64 64 2
32 64 8 4
64 8 16 2
8 8 64 4
9
64 32 0 64
16 0 32 0
8 16 4 8
0 4 32 2
11
32 64 32 16
64 2 32 4
8 16 32 32
4 4 16 64
11
8 16 2 16
8 8 0 0
64 16 32 2
8 16 0 32
10
32 0 16 2
4 8 8 32
32 64 16 16
16 8 2 2
8
0 16 2 0
64 0 8 4
4 0 8 8
8 64 32 4
11
4 64 4 64
2 0 2 16
8 64 4 32
4 4 8 64
8
2 16 8 8
0 8 8 4
64 4 16 16
32 8 8 64
9
8 16 64 64
32 2 64 8
32 4 0 2
16 4 4 2
11
8 2 64 32
4 16 0 32
4 4 4 2
8 0 4 2
8
2 2 64 32
0 16 16 2
8 32 32 2
16 32 4 16
8
32 0 0 8
2 4 0 4
4 2 16 0
0 0 8 64
10
64 8 8 2
16 16 32 2
2 4 8 4
64 16 4 64
10
2 4 0 0
2 16 8 32
8 2 4 32
64 8 2 8
11
8 2 2 0
0 8 8 64
2 2 32 16
8 8 4 32
8
32 32 64 32
32 32 64 32
32 64 32 64
64 64 32 64
#1 16
#2 8
#3 16
#4 64
#5 8
#6 16
#7 32
#8 32
#9 64
#10 64
#11 128
#12 128
#13 128
#14 128
#15 256
#16 256
#17 256
#18 128
#19 256
#20 128
#21 128
#22 128
#23 128
#24 128
#25 128
#26 256
#27 256
#28 128
#29 128
#30 128
#31 256
#32 128
#33 128
#34 256
#35 256
#36 256
#37 256
#38 128
#39 128
#40 128
#41 256
#42 128
#43 256
#44 128
#45 128
#46 128
#47 256
#48 128
#49 128
#50 512
#include<iostream>
using namespace std;
int T;
int K;
int A[4][4];
int Ans;
int queueA[1000];
int rear;
bool isSame(int step, int length){
if(step==0){
return false;
}else{
int start=length-16;
for(int i=16;i>=0;i--){
if(queueA[start-i]!=queueA[length-i]){
return false;
}
}
return true;
}
}
void BT(int step){
if(step==K){
//int maxA=0;
for(int i=0;i<4;i++){
for(int j=0;j<4;j++){
if(A[i][j]>Ans){
Ans=A[i][j];
}
}
}
return;
}
for(int huong=0;huong<4;huong++){
//dich chuyen
if(huong==0){//Left
//Luu lai vi tri cua cua mang
for(int x=0;x<4;x++){
for(int y=0;y<4;y++){
queueA[rear]=A[x][y];
rear++;
}
}
if(isSame(step,rear)==true){
step==K;
break;
}
for(int x=0;x<4;x++){
int index=0;
for(int y=0;y<4;y++){
if(A[x][y]!=0){
if(y<3 && A[x][y]==A[x][y+1]){
A[x][index]=A[x][y]*2;
y++;
index++;
}else{
A[x][index]=A[x][y];
index++;
}
}
}
while(index<4){
A[x][index]=0;
index++;
}
}
}
else if(huong==1){//right
//Luu lai vi tri cua cua mang
for(int x=0;x<4;x++){
for(int y=0;y<4;y++){
queueA[rear]=A[x][y];
rear++;
}
}
if(isSame(step,rear)==true){
step==K;
break;
}
for(int x=0;x<4;x++){
int index=3;
for(int y=3;y>=0;y--){
if(A[x][y]!=0){
if(y>0 && A[x][y]==A[x][y-1]){
A[x][index]=A[x][y]*2;
y--;
index--;
}else{
A[x][index]=A[x][y];
index--;
}
}
}
while(index>=0){
A[x][index]=0;
index--;
}
}
}
else if(huong==2){//down
//Luu lai vi tri cua cua mang
for(int x=0;x<4;x++){
for(int y=0;y<4;y++){
queueA[rear]=A[x][y];
rear++;
}
}
if(isSame(step,rear)==true){
step==K;
break;
}
for(int y=0;y<4;y++){
int index=0;
for(int x=0;x<4;x++){
if(A[x][y]!=0){
if(x<3 && A[x][y]==A[x+1][y]){
A[index][y]=A[x][y]*2;
x++;
index++;
}else{
A[index][y]=A[x][y];
index++;
}
}
}
while(index<4){
A[index][y]=0;
index++;
}
}
}
else if(huong==3){//up
//Luu lai vi tri cua cua mang
for(int x=0;x<4;x++){
for(int y=0;y<4;y++){
queueA[rear]=A[x][y];
rear++;
}
}
if(isSame(step,rear)==true){
step==K;
break;
}
for(int y=0;y<4;y++){
int index=3;
for(int x=3;x>=0;x--){
if(A[x][y]!=0){
if(x>0 && A[x][y]==A[x-1][y]){
A[index][y]=A[x][y]*2;
x--;
index--;
}else{
A[index][y]=A[x][y];
index--;
}
}
}
while(index>=0){
A[index][y]=0;
index--;
}
}
}
BT(step+1);
int temp=step*16;
for(int x=0;x<4;x++){
for(int y=0;y<4;y++){
A[x][y]=queueA[temp];
temp++;
}
}
rear=step*16;
}
}
int main()
{
//freopen("input.txt","r",stdin);
cin>>T;
for (int t=1;t<=T;t++)
{
cin>>K;
for(int i=0;i<4;i++){
for(int j=0;j<4;j++){
cin>>A[i][j];
}
}
Ans=0;
rear=0;
BT(0);
cout<<"#"<<t<<" "<<Ans<<endl;
}
return 0;
}
=================================
#include <iostream>
using namespace std;
int T,K;
int map[4][4];
int maxmax;
#define UP 1
#define DOWN 2
#define LEFT 3
#define RIGHT 4
int mapmap1[4][4];
void convertmapmap1(int huong)
{
//gan lai map1 vao map
if(huong==UP)
{
for(int j=0;j<4;j++)
{
for(int i=0;i<4;i++)
{
if(mapmap1[i][j]==0)
{
continue;
}
for(int ti1=i+1;ti1<4;ti1++)
{
if(mapmap1[ti1][j]==0)
{
continue;
}
if(mapmap1[i][j] == mapmap1[ti1][j])
{
mapmap1[ti1][j] = 0;
mapmap1[i][j] *=2;
for(int i1 =i+1;i1<3;i1++)
{
mapmap1[i1][j] = mapmap1[i1+1][j];
}
mapmap1[3][j] = 0;
break;
}
else
{
break;
}
}
}
int temp[4]={0};
int idx = 0;
for(int tt=0;tt<4;tt++)
{
if(mapmap1[tt][j]!=0)
{
temp[idx++] = mapmap1[tt][j];
}
}
for(int ii=0;ii<4;ii++)
{
mapmap1[ii][j] = temp[ii];
}
}
}
else if(huong==DOWN)
{
for(int j=0;j<4;j++)
{
for(int i=3;i>=0;i--)
{
if(mapmap1[i][j]==0)
{
continue;
}
for(int ti1 = i-1;ti1>=0;ti1--)
{
if(mapmap1[ti1][j]==0)
{
continue;
}
if(mapmap1[i][j] == mapmap1[ti1][j])
{
mapmap1[ti1][j] = 0;
mapmap1[i][j] *=2;
for(int i1 = i-1;i1>0;i1--)
{
mapmap1[i1][j] = mapmap1[i1-1][j];
}
mapmap1[0][j] = 0;
break;
}
else
{
break;
}
}
}
int temp[4]={0};
int idx = 3;
for(int tt=3;tt>=0;tt--)
{
if(mapmap1[tt][j]!=0)
{
temp[idx--] = mapmap1[tt][j];
}
}
for(int ii=0;ii<4;ii++)
{
mapmap1[ii][j] = temp[ii];
}
}
}
else if(huong==LEFT)
{
for(int i=0;i<4;i++)
{
for(int j=0;j<4;j++)
{
if(mapmap1[i][j]==0)
{
continue;
}
for(int tj1 = j+1;tj1<4;tj1++)
{
if(mapmap1[i][tj1]==0)
{
continue;
}
if(mapmap1[i][j] == mapmap1[i][tj1])
{
mapmap1[i][tj1] = 0;
mapmap1[i][j] *=2;
for(int j1 = j+1;j1<3;j1++)
{
mapmap1[i][j1] = mapmap1[i][j1+1];
}
mapmap1[i][3] = 0;
break;
}
else
{
break;
}
}
}
int temp[4]={0};
int idx = 0;
for(int tt=0;tt<4;tt++)
{
if(mapmap1[i][tt]!=0)
{
temp[idx++] = mapmap1[i][tt];
}
}
for(int ii=0;ii<4;ii++)
{
mapmap1[i][ii] = temp[ii];
}
}
}
else if(huong==RIGHT)
{
for(int i=0;i<4;i++)
{
for(int j=3;j>=0;j--)
{
if(mapmap1[i][j]==0)
{
continue;
}
for(int tj1 = j-1;tj1>=0;tj1--)
{
if(mapmap1[i][tj1]==0)
{
continue;
}
if(mapmap1[i][j] == mapmap1[i][tj1])
{
mapmap1[i][tj1] = 0;
mapmap1[i][j] *=2;
for(int j1 = j-1;j1>0;j1--)
{
mapmap1[i][j1] = mapmap1[i][j1-1];
}
mapmap1[i][0] = 0;
break;
}
else
{
break;
}
}
}
int temp[4]={0};
int idx = 3;
for(int tt=3;tt>=0;tt--)
{
if(mapmap1[i][tt]!=0)
{
temp[idx--] = mapmap1[i][tt];
}
}
for(int ii=0;ii<4;ii++)
{
mapmap1[i][ii] = temp[ii];
}
}
}
}
int dastaStep[10];
int last_h = -1;
void BT(int count,int m[4][4],int last_h)
{
int cloneM[4][4];
for(int i=0;i<4;i++)
{
for(int j=0;j<4;j++)
{
cloneM[i][j]=m[i][j];
}
}
if(count>=K)
{
for(int i=0;i<4;i++)
{
for(int j=0;j<4;j++)
{
if(maxmax<m[i][j])
{
maxmax = m[i][j];
}
}
}
return;
}
for(int h=1;h<=4;h++)
{
if(h!=last_h)
{
for(int i=0;i<4;i++)
{
for(int j=0;j<4;j++)
{
mapmap1[i][j]= cloneM[i][j];
}
}
//dastaStep[count]=h;
convertmapmap1(h);
BT(count+1,mapmap1,h);
}
}
}
int main()
{
freopen("input.txt","r",stdin);
cin>>T;
for(int tc=1;tc<=T;tc++)
{
cin>>K;
for(int i=0;i<4;i++)
{
for(int j=0;j<4;j++)
{
cin>>map[i][j];
}
}
maxmax = 0;
BT(0,map,-1);
cout<<"#"<<tc<<" "<<maxmax<<endl;
}
return 0;
}
Editor is loading...