13460번 구슬 탈출 2

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

지난 번 코드 : https://hsdevelopment.tistory.com/3

다시 풀어보았다.

계속 10 초과의 숫자들이 출력되길래 

이상했었다. 85번 째 줄의 if문이 무시되는 상황이었다.

알고보니 쓰레기 값이었다.

그래서 88번 째 줄을 추가해줬더니 통과되었다.

핵심은

빨간 구슬, 파란 구슬 둘 다

O의 위치에서 계속 있으면서 queue가 empty() 될 때 까지 return하지 않는 것이다.

그래야 88번 째 줄에 의해 return -1;이 될 수 있다.

#include <bits/stdc++.h>
 
using namespace std;
 
typedef struct info
{
    int ry;
    int rx;
    int by;
    int bx;
}info;
 
char Map[14][14];
 
int w = 0, h = 0;
 
int dy[4] = { 0, 1, 0, -1 };
int dx[4] = { 1, 0, -1, 0 };
 
pair<int, int> r, b;
 
bool visit[14][14][14][14] = { false, };
 
queue<info> q;
 
int bfs()
{
    int ret = 0;
 
    visit[r.first][r.second][b.first][b.second] = true;
 
    q.push({ r.first, r.second, b.first, b.second });
 
    while (!q.empty())
    {
        int qSize = q.size();
 
        while (qSize--)
        {
            int ry = q.front().ry, rx = q.front().rx;
            int by = q.front().by, bx = q.front().bx;
 
            q.pop();
 
            if (Map[ry][rx] == 'O' && Map[by][bx] != 'O') return ret;
            
            for (int i = 0; i < 4; i++)
            {
                int nry = ry, nrx = rx;
                int nby = by, nbx = bx;
 
                while (Map[nry + dy[i]][nrx + dx[i]] != '#' && Map[nry][nrx] != 'O')
                {
                    nry += dy[i];
                    nrx += dx[i];
                }
 
                while (Map[nby + dy[i]][nbx + dx[i]] != '#' && Map[nby][nbx] != 'O')
                {
                    nby += dy[i];
                    nbx += dx[i];
                }
 
                if (nry == nby && nrx == nbx && Map[nry][nrx] != 'O')
                    if (abs(nry - ry) + abs(nrx - rx) < abs(nby - by) + abs(nbx - bx))
                    {
                        nby -= dy[i];
                        nbx -= dx[i];
                    }
                    else
                    {
                        nry -= dy[i];
                        nrx -= dx[i];
                    }
 
                if (visit[nry][nrx][nby][nbx]) continue;
 
                visit[nry][nrx][nby][nbx] = true;
                q.push({ nry, nrx, nby, nbx });
            }
        }
 
        ++ret;
 
        if (ret > 10) return -1;
    }
 
    return -1;
}
 
int main(void)
{
    scanf("%d %d", &h, &w);
 
    for (int i = 0; i < h; i++)
    {
        scanf("%s", Map[i]);
 
        for (int j = 0; j < w; j++)
            if (Map[i][j] == 'R') r.first = i, r.second = j;
            else if (Map[i][j] == 'B') b.first = i, b.second = j;
    }
 
    printf("%d\n", bfs());
 
    return 0;
}