(C++) 12100번: 2048 (Easy)

Standard

문제 링크: https://www.acmicpc.net/problem/12100

유명한 게임이라 게임 로직 자체는 설명할 필요가 없을 듯.
– [좌/우/상/하]^5 번 움직이는 경우의 수가 있으므로 DFS로 처리.
– 각 블록 별로 merged 맵이 있음. 이 맵은 한 번 이동할 때 merged되지 않은 같은 숫자의 두 블록만 합쳐지고, 다른 경우는 합쳐지지 않게 하는 역할.
– 각 블록이 원하는 방향으로 빈 공간이 있을 때까지 이동. 각 블럭이 빈 공간이 없을 때까지 이동 후, 자기 앞에 있는 블록과 합쳐질 조건이 되는 경우 (둘 다 같은 숫자, 둘 다 merge된 적이 없음) 합쳐지고, 합쳐진 블럭은 merged=1로 설정됨.
– 각 경우 5번 다 움직이고 나서 숫자가 가장 블록을 기록함.

#include <iostream>
#include <cstdlib>

using namespace std;
const int limit = 5;

int numN = 0;
int maxBlock = 0;

void process(int** map);
void process_(int tryNum, char direction, int** map);

int main() {
    cin.tie(NULL);
    ios::sync_with_stdio(false);

    cin >> numN;

    int **map = NULL; // int map[numN][numN]
    map = (int**) malloc (numN * sizeof(int*));
    for (int i = 0; i < numN; i++)
        map[i] = (int*) malloc (numN * sizeof(int));

    for (int i = 0; i < numN; i++) {
        for (int j = 0; j < numN; j++) {
            cin >> map[j][i];
        }
    }

    // It's DFS!
    process(map);

    cout << maxBlock;
}

void process(int** map) {
    process_(1, 'U', map); // to Up
    process_(1, 'D', map); // to Down
    process_(1, 'L', map); // to Left
    process_(1, 'R', map); // to Right
}

void process_(int tryNum, char direction, int** map) {
    int** newMap;
    newMap = (int**) malloc (numN * sizeof(int*));
    for (int i = 0; i < numN; i++)
        newMap[i] = (int*) malloc (numN * sizeof(int));

    for (int i = 0; i < numN; i++) {
        for (int j = 0; j < numN; j++) {
            newMap[j][i] = map[j][i];;
        }
    }

    // always initialize
    int **merged = NULL; // int merged[numN][numN]
    merged = (int**) malloc (numN * sizeof(int*));
    for (int i = 0; i < numN; i++)
        merged[i] = (int*) malloc (numN * sizeof(int));

    for (int i = 0; i < numN; i++) 
        for (int j = 0; j < numN; j++) 
            merged[j][i] = 0;

    switch (direction) {
        case 'U':
            for (int i = 1; i < numN; i++) { // from second row
                for (int j = 0; j < numN; j++) { // from first column
                    for (int k = i; k > 0; k--) { // move upward as much as possible
                        if (newMap[j][k] != 0) {
                            if (newMap[j][k - 1] == 0) { // can move
                                newMap[j][k - 1] = newMap[j][k];
                                merged[j][k - 1] = merged[j][k];
                                newMap[j][k] = 0;
                                merged[j][k] = 0;
                            }
                            else if (newMap[j][k - 1] == newMap[j][k] && merged[j][k - 1] == 0 && merged[j][k] == 0) { // can merge
                                newMap[j][k - 1] *= 2;
                                newMap[j][k] = 0;
                                merged[j][k - 1] = 1;

                                break;
                            }
                        }
                    }
                }
            }
            break;
        case 'D':
            for (int i = numN - 2; i >= 0; i--) { // from second last row
                for (int j = 0; j < numN; j++) { // from first column
                    for (int k = i; k < numN - 1; k++) { // move downward as much as possible
                        if (newMap[j][k] != 0) {
                            if (newMap[j][k + 1] == 0) { // can move
                                newMap[j][k + 1] = newMap[j][k];
                                merged[j][k + 1] = merged[j][k];
                                newMap[j][k] = 0;
                                merged[j][k] = 0;
                            }
                            else if (newMap[j][k + 1] == newMap[j][k] && merged[j][k + 1] == 0 && merged[j][k] == 0) { // can merge
                                newMap[j][k + 1] *= 2;
                                newMap[j][k] = 0;
                                merged[j][k + 1] = 1;

                                break;
                            }
                        }
                    }
                }
            }
            break;
        case 'L':
            for (int i = 1; i < numN; i++) { // from second column
                for (int j = 0; j < numN; j++) { // from first row
                    for (int k = i; k > 0; k--) { // move leftward as much as possible
                        if (newMap[k][j] != 0) {
                            if (newMap[k - 1][j] == 0) { // can move
                                newMap[k - 1][j] = newMap[k][j];
                                merged[k - 1][j] = merged[k][j];
                                newMap[k][j] = 0;
                                merged[k][j] = 0;
                            }
                            else if (newMap[k - 1][j] == newMap[k][j] && merged[k - 1][j] == 0 && merged[k][j] == 0) { // can merge
                                newMap[k - 1][j] *= 2;
                                newMap[k][j] = 0;
                                merged[k - 1][j] = 1;

                                break;
                            }
                        }
                    }
                }
            }
            break;
        case 'R':
            for (int i = numN - 2; i >= 0; i--) { // from second last column
                for (int j = 0; j < numN; j++) { // from first row
                    for (int k = i; k < numN -1; k++) { // move rightward as much as possible
                        if (newMap[k][j] != 0) {
                            if (newMap[k + 1][j] == 0) { // can move
                                newMap[k + 1][j] = newMap[k][j];
                                merged[k + 1][j] = merged[k][j];
                                newMap[k][j] = 0;
                                merged[k][j] = 0;
                            }
                            else if (newMap[k + 1][j] == newMap[k][j] && merged[k + 1][j] == 0 && merged[k][j] == 0) { // can merge
                                newMap[k + 1][j] *= 2;
                                newMap[k][j] = 0;
                                merged[k + 1][j] = 1;

                                break;
                            }
                        }
                    }
                }
            }
            break;
    }

    for (int i = 0; i < numN; i++)
        free(merged[i]);
    free(merged);

    if (tryNum == limit) {
        for (int i = 0; i < numN; i++) {
            for (int j = 0; j < numN; j++) {
                if (maxBlock < newMap[j][i])
                    maxBlock = newMap[j][i];
            }
        }
    }
    else { // proceed more
        process_(tryNum + 1, 'U', newMap); // to Up
        process_(tryNum + 1, 'D', newMap); // to Down
        process_(tryNum + 1, 'L', newMap); // to Left
        process_(tryNum + 1, 'R', newMap); // to Right
    }

    for (int i = 0; i < numN; i++)
        free(newMap[i]);
    free(newMap);

}

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.