12100 2048 (Easy)

12100 2048 (Easy)

*핵심 아이디어 : 

1.지역변수로 tmp배열을 두어 매순간마다 복사하며 사용하였다.

2.block_move 함수의 구현.

*문제풀이

1. 상하좌우 4방향에 대해 움직였을때 처리해줄 block_move 함수 작성.

--> block_move 함수의 주석 참고.

2. 모든경우에 대해 완전탐색.

#include <iostream>
#include <algorithm>
#define P pair<int,int>
#define SZ 20
using namespace std;
 
int n, res;
int map[SZ][SZ];
 
void block_move(int map[][SZ], int dir) {
    //1상,2하,3좌,4우
    if (dir == 1) {
        for (int i = 0; i < n; i++) {
            int ax = 0;
            int bx = ax + 1;
            while (bx <= n - 1) {
                if (map[bx][i] != 0) {
                    //ax가 비어있는경우
                    if (map[ax][i] == 0) {
                        map[ax][i] = map[bx][i];
                        map[bx][i] = 0;
                    }
                    //ax가 비어있지 않은 경우
                    else {
                        //ax와 bx가 같은 경우
                        if (map[ax][i] == map[bx][i]) {
                            map[ax][i] = (map[ax][i] << 1);
                            map[bx][i] = 0;
                            ax++;
                        }
                        //ab와 bx가 다른경우
                        else {
                            //한칸차이
                            if (bx - ax == 1) {
                                ax++;
                            }
                            //두칸 이상 차이
                            else {
                                ax++;
                                map[ax][i] = map[bx][i];
                                map[bx][i] = 0;
                            }
                        }
                    }
                }
                bx++;
            }
        }
    }
    //하
    else if (dir == 2) {
        for (int i = 0; i < n; i++) {
            int ax = n - 1;
            int bx = ax - 1;
            while (bx >= 0) {
                if (map[bx][i] != 0) {
                    if (map[ax][i] == 0) {
                        map[ax][i] = map[bx][i];
                        map[bx][i] = 0;
                    }
                    else {
                        if (map[ax][i] == map[bx][i]) {
                            map[ax][i] = (map[ax][i] << 1);
                            map[bx][i] = 0;
                            ax--;
                        }
                        else {
                            if (ax - bx == 1) {
                                ax--;
                            }
                            else {
                                ax--;
                                map[ax][i] = map[bx][i];
                                map[bx][i] = 0;
                            }
                        }
                    }
                }
                bx--;
            }
        }
    }
    //좌
    else if (dir == 3) {
        for (int i = 0; i < n; i++) {
            int ax = 0;
            int bx = ax + 1;
            while (bx <= n - 1) {
                if (map[i][bx] != 0) {
                    if (map[i][ax] == 0) {
                        map[i][ax] = map[i][bx];
                        map[i][bx] = 0;
                    }
                    else {
                        if (map[i][ax] == map[i][bx]) {
                            map[i][ax] = (map[i][ax] << 1);
                            map[i][bx] = 0;
                            ax++;
                        }
                        else {
                            if (bx - ax == 1) {
                                ax++;
                            }
                            else {
                                ax++;
                                map[i][ax] = map[i][bx];
                                map[i][bx] = 0;
                            }
                        }
                    }
                }
                bx++;
            }
        }
    }
    //우
    else {
        for (int i = 0; i < n; i++) {
            int ax = n - 1;
            int bx = ax - 1;
            while (bx >= 0) {
                if (map[i][bx] != 0) {
                    if (map[i][ax] == 0) {
                        map[i][ax] = map[i][bx];
                        map[i][bx] = 0;
                    }
                    else {
                        if (map[i][ax] == map[i][bx]) {
                            map[i][ax] = (map[i][ax] << 1);
                            map[i][bx] = 0;
                            ax--;
                        }
                        else {
                            if (ax - bx == 1) {
                                ax--;
                            }
                            else {
                                ax--;
                                map[i][ax] = map[i][bx];
                                map[i][bx] = 0;
                            }
                        }
                    }
                }
                bx--;
            }
        }
    }
}
 
//디버깅용
void printAll(int map[][SZ]) {
    cout << endl;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << map[i][j] << " ";
        }
        cout << endl;
    }
}
 
int getResult(int tmp[][SZ]) {
    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            ans = max(ans, tmp[i][j]);
        }
    }
    return ans;
}
 
void dfs(int map[][SZ], int dir, int cnt) {
 
    if (cnt == 6) {
        res = max(res, getResult(map));
    }
    else {
        int tmp[SZ][SZ];
        //배열 복사
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                tmp[i][j] = map[i][j];
            }
        }
 
        block_move(tmp, dir);
        for (int i = 1; i < 5; i++) {
            dfs(tmp, i, cnt + 1);
        }
    }
}
 
int main() {
    ios_base::sync_with_stdio(false);
 
    cin >> n;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> map[i][j];
        }
    }
 
    for (int i = 1; i < 5; i++) {
        dfs(map, i, 1);
    }
 
    cout << res << endl;
 
    return 0;
}