12100 2048 (Easy)

https://www.acmicpc.net/problem/12100

2048 게임을 최대 5번 이동해서 만들 수 있는 가장 큰 블럭의 값을 구하는 문제이다. 일단 상하좌우 4가지 경우에 대하여 4^5=1024개의 경우를 모두 만든다. 그리고 실제로 블럭들을 이동시켜 본다. 해당 방향에 대하여 먼저 블럭들 사이에 빈칸이 없게 밀고나서 인접한 블럭의 값들이 같으면 합쳐준다. 이 때 합친 후에 블럭 사이에 빈칸이 다시 생기므로 한번 더 밀어야 한다.

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
 
int n,board[20][20],ans;
vector<int> path;
 
int solve()
{
    int b[20][20];
    for(int i=0;i<n;i++) for(int j=0;j<n;j++)
        b[i][j]=board[i][j];
 
    for(int k=0;k<5;k++)
    {
        if(path[k]==1) // 상
        {
            for(int j=0;j<n;j++) // 위로 밀기
            {
                int idx=0;
                for(int i=0;i<n;i++)
                {
                    if(b[i][j]!=0)
                    {
                        if(i==idx) idx++;
                        else b[idx][j]=b[i][j],b[i][j]=0,idx++;
                    }
                }
            }
            for(int j=0;j<n;j++) for(int i=0;i<n-1;i++) // 블럭 합치기
                if(b[i][j]==b[i+1][j]) b[i][j]*=2,b[i+1][j]=0;
            for(int j=0;j<n;j++) // 다시 위로 밀기
            {
                int idx=0;
                for(int i=0;i<n;i++)
                {
                    if(b[i][j]!=0)
                    {
                        if(i==idx) idx++;
                        else b[idx][j]=b[i][j],b[i][j]=0,idx++;
                    }
                }
            }
        }
        else if(path[k]==2) // 하
        {
            for(int j=0;j<n;j++)
            {
                int idx=n-1;
                for(int i=n-1;i>=0;i--)
                {
                    if(b[i][j]!=0)
                    {
                        if(i==idx) idx--;
                        else b[idx][j]=b[i][j],b[i][j]=0,idx--;
                    }
                }
            }
            for(int j=0;j<n;j++) for(int i=n-1;i>0;i--)
                if(b[i][j]==b[i-1][j]) b[i][j]*=2,b[i-1][j]=0;
            for(int j=0;j<n;j++)
            {
                int idx=n-1;
                for(int i=n-1;i>=0;i--)
                {
                    if(b[i][j]!=0)
                    {
                        if(i==idx) idx--;
                        else b[idx][j]=b[i][j],b[i][j]=0,idx--;
                    }
                }
            }
        }
        else if(path[k]==3) // 좌
        {
            for(int i=0;i<n;i++)
            {
                int idx=0;
                for(int j=0;j<n;j++)
                {
                    if(b[i][j]!=0)
                    {
                        if(j==idx) idx++;
                        else b[i][idx]=b[i][j],b[i][j]=0,idx++;
                    }
                }
            }
            for(int i=0;i<n;i++) for(int j=0;j<n-1;j++)
                if(b[i][j]==b[i][j+1]) b[i][j]*=2,b[i][j+1]=0;
            for(int i=0;i<n;i++)
            {
                int idx=0;
                for(int j=0;j<n;j++)
                {
                    if(b[i][j]!=0)
                    {
                        if(j==idx) idx++;
                        else b[i][idx]=b[i][j],b[i][j]=0,idx++;
                    }
                }
            }
        }
        else if(path[k]==4) // 우
        {
            for(int i=0;i<n;i++)
            {
                int idx=n-1;
                for(int j=n-1;j>=0;j--)
                {
                    if(b[i][j]!=0)
                    {
                        if(j==idx) idx--;
                        else b[i][idx]=b[i][j],b[i][j]=0,idx--;
                    }
                }
            }
            for(int i=0;i<n;i++) for(int j=n-1;j>0;j--)
                if(b[i][j]==b[i][j-1]) b[i][j]*=2,b[i][j-1]=0;
            for(int i=0;i<n;i++)
            {
                int idx=n-1;
                for(int j=n-1;j>=0;j--)
                {
                    if(b[i][j]!=0)
                    {
                        if(j==idx) idx--;
                        else b[i][idx]=b[i][j],b[i][j]=0,idx--;
                    }
                }
            }
        }
    }
 
    int ret=0;
    for(int i=0;i<n;i++) for(int j=0;j<n;j++)
        ret=max(ret,b[i][j]);
    return ret;
}
 
void go(int cnt) // 1:상 2:하 3:좌 4:우
{
    if(cnt==5)
    {
        ans=max(ans,solve());
        return;
    }
 
    for(int i=1;i<=4;i++)
    {
        path.push_back(i);
        go(cnt+1);
        path.pop_back();
    }
}
 
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++) for(int j=0;j<n;j++)
        scanf("%d",&board[i][j]);
    go(0);
    printf("%d\n",ans);
    return 0;
}