12100 2048 (Easy)

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

12100번: 2048 (Easy)

 

온라인게임으로 했던 2048 게임을 구현하는 문제이다.

 

https://play2048.co/

2048

 

5번까지 움직여서 나오는 최대 숫자는 무언인지 출력하는 문제.

 

4방향을 움직여야하는데, 방향마다 움직이는 순서(우선순위)가 제각각이다보니 일반화하기가 까다로웠다.

예를 들어, 왼쪽으로 움직였을 때를 생각해보면

1. 모든 타일을 왼쪽으로 움직인다.

2. 맨 왼쪽부터 같은 숫자가 나오면 둘 중에 더 왼쪽에 있는 타일에 합쳐주고 다른 타일은 0으로 만든다.

3. 합쳐져서 0이된 칸을 없애기 위해 다시 모든 타일을 왼쪽으로 움직인다.

 

2번과정을 보면 맨 왼쪽부터 타일을 합쳐주는 작업을 한다. 오른쪽으로 움직였을 때는 오른쪽부터, 위쪽으로 움직였을 때는 위쪽부터 움직여줘야한다.

결국 일반화하지 않고 모든 방향에 대해서 함수를 만들었다.

 

 

 

#include <bits/stdc++.h>
 
using namespace std;
 
#define swap(a,b) (a)^=(b)^=(a)^=(b)
#define endl '\n'
#define int long long
 
using pii = pair<int, int>;
 
const double EPS = 1e-9;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};
 
int mx, n;
 
void addLeft(vector<vector<int>>& v);
void addRight(vector<vector<int>>& v);
void addUp(vector<vector<int>>& v);
void addDown(vector<vector<int>>& v);
 
void moveLeft(vector<vector<int>>& v);
void moveRight(vector<vector<int>>& v);
void moveUp(vector<vector<int>>& v);
void moveDown(vector<vector<int>>& v);
 
void LEFT(vector<vector<int>>& v);
void RIGHT(vector<vector<int>>& v);
void UP(vector<vector<int>>& v);
void DOWN(vector<vector<int>>& v);
 
 
void recursive(int pos, vector<vector<int>> v)
{
    for(size_t i=0;i<v.size();i++)
            for(size_t j=0;j<v[i].size();j++)
                mx = max(v[i][j], mx);
    if(pos == 5) return;
    vector<vector<int>> left(v), right(v), up(v), down(v);
    LEFT(left);
    recursive(pos+1, left);
    RIGHT(right);
    recursive(pos+1, right);
    UP(up);
    recursive(pos+1, up);
    DOWN(down);
    recursive(pos+1, down);
 
}
 
int32_t main()
{
    cin.sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n;
    vector<vector<int>> initial(n, vector<int>(n, 0));
    for(int i=0;i<n;i++) 
        for(int j=0;j<n;j++)
            cin >> initial[i][j];
 
    recursive(0, initial);
    
    cout << mx;
 
    return 0;
}
 
void addLeft(vector<vector<int>>& v)
{
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n-1;j++)
        {
            if(v[i][j] == v[i][j+1])
            {
                v[i][j] += v[i][j+1];
                v[i][j+1] = 0;
            }
        }
    }
}
 
void addRight(vector<vector<int>>& v)
{
    for(int i=0;i<n;i++)
    {
        for(int j=n-1;j>0;j--)
        {
            if(v[i][j] == v[i][j-1])
            {
                v[i][j] += v[i][j-1];
                v[i][j-1] = 0;
            }
        }
    }
}
 
void addUp(vector<vector<int>>& v)
{
    for(int i=0;i<n-1;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(v[i][j] == v[i+1][j])
            {
                v[i][j] += v[i+1][j];
                v[i+1][j] = 0;
            }
        }
    }
}
 
void addDown(vector<vector<int>>& v)
{
    for(int i=n-1;i>0;i--)
    {
        for(int j=0;j<n;j++)
        {
            if(v[i][j] == v[i-1][j])
            {
                v[i][j] += v[i-1][j];
                v[i-1][j] = 0;
            }
        }
    }
}
void moveLeft(vector<vector<int>>& v)
{
    for(size_t i=0;i<v.size();i++)
    {
        for(size_t j=0;j<v[i].size();j++)
        {
            int y = i, x = j;
            if(v[y][x])
            {
                while( x>0 && v[y][x-1] == 0) x--;
                if(y == i && x == j) continue;
                v[y][x] = v[i][j];
                v[i][j] = 0;
            }
        }
    }
}
 
void moveRight(vector<vector<int>>& v)
{
    for(int i=0;i<n;i++)
    {
        for(int j=n-1;j>=0;j--)
        {
            int y = i, x = j;
            if(v[y][x])
            {
                while( x < n-1 && v[y][x+1] == 0) x++;
                if(y == i && x == j) continue;
                v[y][x] = v[i][j];
                v[i][j] = 0;
            }
        }
    }
}
 
void moveUp(vector<vector<int>>& v)
{
    for(size_t i=0;i<v.size();i++)
    {
        for(size_t j=0;j<v[i].size();j++)
        {
            int y = i, x = j;
            if(v[y][x])
            {
                while( y>0 && v[y-1][x] == 0) y--;
                if(y == i && x == j) continue;
                v[y][x] = v[i][j];
                v[i][j] = 0;
            }
        }
    }
}
 
void moveDown(vector<vector<int>>& v)
{
    for(int i=n-1;i>=0;i--)
    {
        for(size_t j=0;j<v[i].size();j++)
        {
            int y = i, x = j;
            if(v[y][x])
            {
                while( y < n-1 && v[y+1][x] == 0) y++;
                if(y == i && x == j) continue;
                v[y][x] = v[i][j];
                v[i][j] = 0;
            }
        }
    }
}
 
void LEFT(vector<vector<int>>& v)
{
    moveLeft(v);
    addLeft(v);
    moveLeft(v);
}
 
void RIGHT(vector<vector<int>>& v)
{
    moveRight(v);
    addRight(v);
    moveRight(v);
}
 
void UP(vector<vector<int>>& v)
{
    moveUp(v);
    addUp(v);
    moveUp(v);
}
 
void DOWN(vector<vector<int>>& v)
{
    moveDown(v);
    addDown(v);
    moveDown(v);
}