BOJ)13460 구슬탈출2

문제: icpc.me/13460

빨간 공과 파란 공이 동시에 움직일 때 빨간공을 구멍에 넣게하는 최소 횟수를 출력하는 문제이다.

우리는 빨간공과 파란공의 위치를 동시에 조작하며 BFS를 돌리며 횟수를 출력한다. 이 때 공이 겹치는 경우를 잘 처리해주어야 한다.

#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
int n, m, disc[11][11][11][11], bx, by, rx, ry;
char a[11][11];
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
int bfs() {
    queue<pair<pair<int, int>, pair<int,int>>> qu;
    qu.push({ {rx,ry},{bx,by} });
    disc[rx][ry][bx][by] = 1;
    int ret = 0;
    while (qu.size()) {
        int qs = qu.size();
        while (qs--) {
            int x = qu.front().first.first;
            int y = qu.front().first.second;
            int z = qu.front().second.first;
            int w = qu.front().second.second;
            qu.pop();
            if (a[x][y] == 'O'&&a[x][y] != a[z][w])
                return ret;
            for (int i = 0; i < 4; i++) {
                int cx = x, cy = y, cz = z, cw = w;
                while (a[cx + dx[i]][cy + dy[i]] != '#'&&a[cx][cy] != 'O') {
                    cx += dx[i];
                    cy += dy[i];
                }
                while (a[cz + dx[i]][cw + dy[i]] != '#'&&a[cz][cw] != 'O') {
                    cz += dx[i];
                    cw += dy[i];
                }
                if (cx == cz&&cy == cw) {
                    if (a[cx][cy] == 'O')continue;
                    if (abs(cx - x) + abs(cy - y) < abs(cz - z) + abs(cw - w)) {
                        cz -= dx[i];
                        cw -= dy[i];
                    }
                    else {
                        cx -= dx[i];
                        cy -= dy[i];
                    }
                }
                if (disc[cx][cy][cz][cw])continue;
                qu.push({ {cx,cy} ,{cz,cw} });
                disc[cx][cy][cz][cw] = 1;
            }
        }
        if (ret == 10)
            return -1;
        ret++;
    }
    return -1;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) {
        getchar();
        for (int j = 0; j < m; j++) {
            scanf("%c", &a[i][j]);
            if (a[i][j] == 'B') {
                bx = i;
                by = j;
            }
            else if (a[i][j] == 'R') {
                rx = i;
                ry = j;
            }
        }
    }
    printf("%d\n", bfs());
    return 0;
}

'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)1058 친구  (0)	2017.04.03
BOJ)12100 2048 (Easy)  (0)	2017.03.30
BOJ)13460 구슬탈출2  (6)	2017.03.30
BOJ)1520 내리막 길  (0)	2017.03.30
BOJ)10422 괄호  (0)	2017.03.30
BOJ)1194 달이 차오른다, 가자.  (0)	2017.03.30