백준 13460 : 구슬 탈출 2

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

13460번: 구슬 탈출 2

 

#include <iostream>
#include <queue>
 
struct coord
{
    int y;
    int x;
}R, B;
 
int N, M;
 
int dy[4] = { 1, 0, -1, 0 };
int dx[4] = { 0, 1, 0, -1 };
 
char board[11][11];
 
void input()
{
    std::cin >> N >> M;
    for (int y = 1; y <= N; ++y)
    {
        for (int x = 1; x <= M; ++x)
        {
            std::cin >> board[y][x];
            if (board[y][x] == 'R')
            {
                board[y][x] = '.';
                R = { y, x };
            }
            if (board[y][x] == 'B')
            {
                board[y][x] = '.';
                B = { y, x };
            }
        }
    }
}
 
void print(int ry, int rx, int by, int bx)
{
    std::cout << '\n';
    for (int y = 1; y <= N; ++y)
    {
        for (int x = 1; x <= M; ++x)
        {
            if (y == ry && x == rx)
            {
                std::cout << 'R' << ' ';
            }
            else if (y == by && x == bx)
            {
                std::cout << 'B' << ' ';
            }
            else
            {
                std::cout << board[y][x] << ' ';
            }
        }
        std::cout << '\n';
    }
}
 
int solve()
{
    std::queue<std::pair<std::pair<coord, coord>, std::pair<int, int>>> bfs;
    bfs.push({ { R, B }, { 1, 4 } });
    int ans = 0;
    while (bfs.empty() == false)
    {
        coord rPos = bfs.front().first.first;
        coord bPos = bfs.front().first.second;
        int cnt = bfs.front().second.first;
        int flag = bfs.front().second.second;
        bfs.pop();
        if (cnt > 10)
        {
            continue;
        }
 
        //print(0, 0, 0, 0);
        //std::cout << "----------------------------------------------------------\n";
        for (int i = 0; i < 4; ++i)
        {
            if (flag != 4 && flag % 2 == 0 && i % 2 == 0)
            {
                continue;
            }
            if (flag != 4 && flag % 2 == 1 && i % 2 == 1)
            {
                continue;
            }
            bool chk = false;
            coord rNext = rPos;
            coord bNext = bPos;
            int rCnt = 0;
            int bCnt = 0;
            while (board[rNext.y][rNext.x] == '.')
            {
                rNext.y += dy[i];
                rNext.x += dx[i];
                ++rCnt;
            }
            rNext.y -= dy[i];
            rNext.x -= dx[i];
 
            while (board[bNext.y][bNext.x] == '.')
            {
                bNext.y += dy[i];
                bNext.x += dx[i];
                ++bCnt;
            }
//             if (board[bNext.y][bNext.x] == 'O')
//             {
//                 continue;
//             }
            bNext.y -= dy[i];
            bNext.x -= dx[i];
            if (bNext.y == rNext.y && bNext.x == rNext.x && board[rNext.y + dy[i]][rNext.x + dx[i]] == 'O')
            {
                continue;
            }
 
            if (rNext.y == bNext.y && rNext.x == bNext.x)
            {
                coord* ptr = nullptr;
                if (rCnt < bCnt)
                {
                    ptr = &bNext;
                }
                else
                {
                    ptr = &rNext;
                }
                ptr->y -= dy[i];
                ptr->x -= dx[i];
            }
 
            if (board[rNext.y + dy[i]][rNext.x + dx[i]] == 'O')
            {
                return cnt;
            }
            if (board[bNext.y + dy[i]][bNext.x + dx[i]] == 'O')
            {
                continue;
            }
            //print(rNext.y, rNext.x, bNext.y, bNext. x);
            if (rNext.y != rPos.y || rNext.x != rPos.x || bNext.y != bPos.y || bNext.x != bPos.x)
            {
                bfs.push({ {rNext, bNext}, { cnt + 1, i } });
            }
        }
    }
    return -1;
}
 
int main()
{
    input();
    std::cout << solve();
    return 0;
}

 

테스트케이스를 돌려보기 전에 먼저

 

실수한 부분이 없는지(오타 등), 내 생각대로 코드가 흘러가는지

 

먼저 생각해보고

 

그 뒤에도 틀린다면 예외를 생각해보자