(C++) 13460번: 구슬 탈출 2

Standard

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

[좌/우/상/하]^10 번 움직여서 변화를 트래킹하면 됨. 그래서 DFS로 분류함. 
– 왼쪽/오른쪽/위/아래 로 움직일 때 누가 먼저 움직이는지 체크함. 왼쪽/오른쪽은 같은 가로줄에 있을 때, 위/아래는 같은 세로줄에 있을 때 확인 필요. 아닌 경우 상관 없음.
– 각 구슬 별로 지정된 방향으로 이동. 빈 공간이면 이동, 구멍이면 빠져나감 (구슬 좌표 -1, -1로), 벽이거나 다른 구슬이 있으면 움직이지 않음. 다 움직이고 나면 최종 구슬 좌표 업데이트.
– 두 구슬 다 업데이트가 되고 나면 우선 파란 구슬이 구멍으로 나갔는지 확인 (실패 여부 확인). 파란 구슬이 나가지 않았으면 다음 빨간 구슬이 구멍으로 나갔는지 확인 (성공 여부 확인). 두 구슬 다 밖이 아니면 다음 단계로 진행.
– 10번 움직이고 나서도 두 구슬이 밖으로 나가지 않았으면 실패로 처리.

– DFS 처리가 끝나고 나면 최소로 움직인 횟수 (실패면 -1) 출력.

#include <iostream>
#include <cstdlib>

using namespace std;

char** map = NULL; // char map[numN][numM]
int numTrial = 11;
int numN = 0, numM = 0;

void process(int redR, int redC, int blueR, int blueC);
void process_(int tryNum, char direction, int redR, int redC, int blueR, int blueC);

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

    cin >> numN; // row
    cin >> numM; // column
    
    map = (char**) malloc (numN * sizeof(char*));
    for (int i = 0; i < numN; i++) 
        map[i] = (char*) malloc (numM * sizeof(char));
    
    int redBallRow = 0, redBallColumn = 0;
    int blueBallRow = 0, blueBallColumn = 0;
    int exitRow = 0, exitColumn = 0;
    
    char* tmp = (char*) malloc ((numM + 1) * sizeof(char));
    for (int i = 0; i < numN; i++) {
        cin >> tmp;
        for (int j = 0; j < numM; j++) {
            map[i][j] = tmp[j];
            if (map[i][j] == 'B') {
                blueBallRow = i;
                blueBallColumn = j;
            }
            else if (map[i][j] == 'R') {
                redBallRow = i;
                redBallColumn = j;
            }
            else if (map[i][j] == 'O') {
                exitRow = i;
                exitColumn = j;
            }            
        }
    }

    process(redBallRow, redBallColumn, blueBallRow, blueBallColumn);
    if (numTrial != 11)
        cout << numTrial;
    else
        cout << -1;
}

void process(int redR, int redC, int blueR, int blueC) {
    process_(1, 'L', redR, redC, blueR, blueC);
    process_(1, 'R', redR, redC, blueR, blueC);
    process_(1, 'U', redR, redC, blueR, blueC);
    process_(1, 'D', redR, redC, blueR, blueC);
}

void process_(int tryNum, char direction, int redR, int redC, int blueR, int blueC) {
    int newRedR = redR, newRedC = redC;
    int newBlueR = blueR, newBlueC = blueC;

    char order[2] = {' ', ' '};

    // try to move
    // 1. who to start first?
    switch (direction) {
        case 'L':
            if (newRedR == newBlueR && newBlueC < newRedC) {
                order[0] = 'B';
                order[1] = 'R';
            }
            else {
                order[0] = 'R';
                order[1] = 'B';
            }
            break;
        case 'R':
            if (newRedR == newBlueR && newBlueC > newRedC) {
                order[0] = 'B';
                order[1] = 'R';
            }
            else {
                order[0] = 'R';
                order[1] = 'B';
            }
            break;
        case 'U':
            if (newRedC == newBlueC && newBlueR < newRedR) {
                order[0] = 'B';
                order[1] = 'R';
            }
            else {
                order[0] = 'R';
                order[1] = 'B';
            }
            break;
        case 'D':
            if (newRedC == newBlueC && newBlueR > newRedR) {
                order[0] = 'B';
                order[1] = 'R';
            }
            else {
                order[0] = 'R';
                order[1] = 'B';
            }
            break;
    }

    // 2. move
    for (int i = 0; i < 2; i++) { 
        int curR = 0, curC = 0;
        if (order[i] == 'R') {
            curR = newRedR;
            curC = newRedC;
        }
        else {
            curR = newBlueR;
            curC = newBlueC;
        }

        switch (direction) {
            case 'L':
                for (int j = curC - 1; j >= 0; j--) {
                    if (map[curR][j] == '.') 
                        curC = j;
                    else if (map[curR][j] == 'O') {
                        curR = -1;
                        curC = -1;
                        break;
                    }
                    else if (map[curR][j] == '#') 
                        break;
                    else if (map[curR][j] == 'B') 
                        break;
                    else if (map[curR][j] == 'R') 
                        break;                    
                }
                break;
            case 'R':
                for (int j = curC + 1; j < numM; j++) {
                    if (map[curR][j] == '.') 
                        curC = j;
                    else if (map[curR][j] == 'O') {
                        curR = -1;
                        curC = -1;
                        break;
                    }
                    else if (map[curR][j] == '#') 
                        break;
                    else if (map[curR][j] == 'B') 
                        break;
                    else if (map[curR][j] == 'R') 
                        break;       
                }
                break;
            case 'U':
                for (int j = curR - 1; j >= 0; j--) {
                    if (map[j][curC] == '.') 
                        curR = j;
                    else if (map[j][curC] == 'O') {
                        curR = -1;
                        curC = -1;
                        break;
                    }
                    else if (map[j][curC] == '#') 
                        break;
                    else if (map[j][curC] == 'B') 
                        break;
                    else if (map[j][curC] == 'R') 
                        break;       
                }
                break;
            case 'D':
                for (int j = curR + 1; j < numN; j++) {
                    if (map[j][curC] == '.') 
                        curR = j;
                    else if (map[j][curC] == 'O') {
                        curR = -1;
                        curC = -1;
                        break;
                    }
                    else if (map[j][curC] == '#') 
                        break;
                    else if (map[j][curC] == 'B') 
                        break;
                    else if (map[j][curC] == 'R') 
                        break;       
                }
                break;
        }

        if (order[i] == 'R') {
            newRedR = curR;
            newRedC = curC;

            map[redR][redC] = '.';
            if (newRedR != -1 && newRedC != -1)
                map[newRedR][newRedC] = 'R';
        }
        else {
            newBlueR = curR;
            newBlueC = curC;

            map[blueR][blueC] = '.';
            if (newBlueR != -1 && newBlueC != -1)
                map[newBlueR][newBlueC] = 'B';
        }
    }

    if (newBlueR == -1 && newBlueC == -1) { // fail
        // don't proceed, just restore
        map[blueR][blueC] = 'B';
        map[redR][redC] = 'R';
        if (newRedR != -1 && newRedC != -1)
            map[newRedR][newRedC] = '.';
    }
    else if (newRedR == -1 && newRedC == -1) { // success
        // update
        if (numTrial > tryNum)
            numTrial = tryNum;

        // restore
        map[blueR][blueC] = 'B';
        map[newBlueR][newBlueC] = '.';
        map[redR][redC] = 'R';
    }
    else { // proceed more
        if (tryNum == 10) { // can't proceed more
            // don't proceed, just restore
            map[blueR][blueC] = 'B';
            map[newBlueR][newBlueC] = '.';
            map[redR][redC] = 'R';
            map[newRedR][newRedC] = '.';
        }
        else {
            // proceed
            process_(tryNum + 1, 'L', newRedR, newRedC, newBlueR, newBlueC);
            process_(tryNum + 1, 'R', newRedR, newRedC, newBlueR, newBlueC);
            process_(tryNum + 1, 'U', newRedR, newRedC, newBlueR, newBlueC);
            process_(tryNum + 1, 'D', newRedR, newRedC, newBlueR, newBlueC);

            // restore
            map[blueR][blueC] = 'B';
            map[newBlueR][newBlueC] = '.';
            map[redR][redC] = 'R';
            map[newRedR][newRedC] = '.';
        }
    }
}

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.