5427번 불

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

벽 부수고 이동하기 문제류와 비슷하다.

이런 BFS 유형은 틀리면 안 된다.

#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
 
using namespace std;
 
char Map[1001][1001];
 
int dy[4] = { -1, 0, 1, 0 };
int dx[4] = { 0, -1, 0, 1 };
 
int w = 0, h = 0;
 
bool visit[1001][1001][2] = { false, };
 
vector<pair<int, int> > v;
 
int sy = 0, sx = 0;
 
// 0 : 불, 1 : 상근이
 
int BFS()
{
    queue<pair<pair<int, int>, int> > q;
 
    for (int i = 0; i < v.size(); i++)
    {
        q.push({ { v.at(i).first, v.at(i).second }, 0 });
 
        visit[v.at(i).first][v.at(i).second][0] = true;
    }
 
    q.push({ {sy, sx}, 1 });
 
    visit[sy][sx][1] = true;
 
    int ret = 1;
 
    while (!q.empty())
    {
        int qSize = q.size();
 
        while (qSize--)
        {
            int r = q.front().first.first;
            int c = q.front().first.second;
            int sit = q.front().second;
 
            q.pop();
 
            if ( (r == 0 || r == h - 1 || c == 0 || c == w - 1) && sit == 1)
            {
                return ret;    
            }
 
            if (sit == 0)
            {
                // 불
 
                for (int i = 0; i < 4; i++)
                {
                    int y = r + dy[i];
                    int x = c + dx[i];
 
                    if (y < 0 || y >= h || x < 0 || x >= w) continue;
 
                    if (Map[y][x] == '.' && !visit[y][x][0])
                    {
                        visit[y][x][0] = true;
                        q.push({ {y, x}, 0 });
                        Map[y][x] = '*';
                    }
                }
            }
            else if (sit == 1)
            {
                // 상근이
 
                for (int i = 0; i < 4; i++)
                {
                    int y = r + dy[i];
                    int x = c + dx[i];
 
                    if (y < 0 || y >= h || x < 0 || x >= w || Map[y][x] == '*' || Map[y][x] == '#' || visit[y][x][1]) continue;
 
                    q.push({ {y,x}, 1 });
                    visit[y][x][1] = true;
                }
            }
        }
 
        ++ret;
    }
 
    return -1;
}
 
int main(void)
{
    int T = 0;
 
    scanf("%d", &T);
 
    for (int i = 0; i < T; i++)
    {
        scanf("%d %d", &w, &h);
 
        for (int j = 0; j < h; j++)
        {
            for (int k = 0; k < w; k++)
            {
                cin >> Map[j][k];
 
                if (Map[j][k] == '*')
                {
                    v.push_back({ j, k });
                }
                else if (Map[j][k] == '@')
                {
                    sy = j;
                    sx = k;
                    Map[j][k] = '.';
                }
            }
        }
 
        int result = BFS();
 
        if (result != -1) printf("%d\n", result);
        else printf("IMPOSSIBLE\n");
 
        if(!v.empty()) v.clear();
        memset(Map, 0, sizeof(Map));
        memset(visit, false, sizeof(visit));
    }
 
    return 0;
}