[BOJ-13460]째로탈출2

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

[문제요약]

https://www.acmicpc.net/problem/13459 와 동일한 문제인데, 이 경우에는 10번이하로 움직여서 뺄 수 있는 최소 이동 횟수를 출력하는 문제이다.

[입력]

맵 크기

맵 정보

[출력]

10번 이하로 움직여서 뺄 수 있는

최소 이동 횟수를 출력한다.

혹은

최소 이동 횟수가 없다면 -1을 출력한다.

[접근방법]

방금전에 푼 [BOJ-13459]째로탈출 코드 : http://wondy1128.tistory.com/145

로 쓰지않고, 새로 작성했다. 

DFS로 한 것은 똑같은데 문제의 조건에서 이미 벽으로 다 둘러쌓여있다는 것이 전제이므로 제거하였다.

그리고 이전에 이동했던 방향으로 다시 이동하지 않으므로 가지치기, 반대 방향또한 하지 않으므로 가지치기 할 수 있다.

DFS 인자로는 시도횟수, red위치, blue위치, 맵정보, 이전에이동시킨방향 을 담고  DFS를 돌리면 해결할 수 있다.

처음에 116ms 를 받아서 0ms로 줄이려고 가지치기를 계속해서 시도했다. 다행히 위에 적은 가지치기 방법으로 0ms를 얻을 수 있었다.

[C++ source Code DFS]

#include<cstdio>
const int dr[] = { 0, -1, 0, 1 };
const int dc[] = { 1, 0, -1, 0 };
const int M = 11;
const int INF = 111;
int ROW, COL;
 
struct pos {
    int r, c;
};
 
int mn2(int a, int b) {
    return (a > b) ? b : a;
}
 
int dfs(int tried, pos red, pos blue, char mp[][M], int prev_dir) {
    int ret = INF;
    if (tried > 9) return ret;
 
    for (int i = 0; i < 4; i++) {
        if (prev_dir == i) continue;
        if (prev_dir == ((i + 2) % 2)) continue;
        char nimap[M][M];
        for (int r = 0; r < ROW; r++)
            for (int c = 0; c < COL; c++) nimap[r][c] = mp[r][c]; // copy map
        int hr_r = red.r;
        int hr_c = red.c;
        int hb_r = blue.r;
        int hb_c = blue.c;
        bool red_ok = false;
        bool blue_ok = false;
        bool blue_is_wall = false;
        while (1) {
            int tr_r = hr_r + dr[i];
            int tr_c = hr_c + dc[i];
            char& red_here = nimap[hr_r][hr_c];
            char& red_next = nimap[tr_r][tr_c];
            if (red_next == '.') {
                red_next = 'R';
                red_here = '.';
                hr_r = tr_r;
                hr_c = tr_c;
            }
            else if (red_next == 'O') {
                hr_r = tr_r;
                hr_c = tr_c;
                red_here = '.';
                red_ok = true;
                break;
            }
            else if (red_next == 'B') {
                if (blue_is_wall) break;
                while (1) {
                    int tb_r = hb_r + dr[i];
                    int tb_c = hb_c + dc[i];
                    char& blue_here = nimap[hb_r][hb_c];
                    char& blue_next = nimap[tb_r][tb_c];
                    if (blue_next == '.') {
                        blue_next = 'B';
                        blue_here = '.';
                        hb_r = tb_r;
                        hb_c = tb_c;
                    }
                    else if (blue_next == 'O') {
                        hb_r = tb_r;
                        hb_c = tb_c;
                        blue_here = '.';
                        blue_is_wall = true;
                        blue_ok = true;
                        break;
                    }
                    else if (blue_next == '#') {
                        blue_is_wall = true;
                        break;
                    }
                } // blue
            }
            else if (red_next == '#') {
                break;
            }
        } // red
 
        if (!blue_is_wall) {
            while (1) {
                int tb_r = hb_r + dr[i];
                int tb_c = hb_c + dc[i];
                char& blue_here = nimap[hb_r][hb_c];
                char& blue_next = nimap[tb_r][tb_c];
                if (blue_next == '.') {
                    blue_next = 'B';
                    blue_here = '.';
                    hb_r = tb_r;
                    hb_c = tb_c;
                }
                else if (blue_next == 'O') {
                    hb_r = tb_r;
                    hb_c = tb_c;
                    blue_here = '.';
                    blue_ok = true;
                    break;
                }
                else if (blue_next == '#' || blue_next == 'R') {
                    break;
                }
            } // blue
        }
 
        pos nred;
        nred.r = hr_r;
        nred.c = hr_c;
        pos nblue;
        nblue.r = hb_r;
        nblue.c = hb_c;
 
        if (red_ok && !blue_ok) {
            ret = mn2(tried + 1, ret);            
        }
        else if (!red_ok && !blue_ok) {
            ret = mn2(ret, dfs(tried + 1, nred, nblue, nimap, i));
        }
    }
    return ret;
}
 
int main() {
    char imap[M][M];
    scanf("%d%d", &ROW, &COL);
    pos red;
    pos blue;
    for (int r = 0; r < ROW; r++) {
        scanf("%s", imap[r]);
        for (int c = 0; c < COL; c++) {
            if (imap[r][c] == 'R') red.r = r, red.c = c;
            else if (imap[r][c] == 'B') blue.r = r, blue.c = c;
        }
    } // input
 
    int ans = 111;
    ans = dfs(0, red, blue, imap, -1);
    if (ans == INF) puts("-1");
    else printf("%d", ans);
 
    return 0;
}