[5427] 불

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

이 문제는 ..전형적인 BFS문제라고 할 수 있습니다..

제 주변에 큐를 두개를 써서 푸시는 분들이 꽤 계신데..

저는 큐를 하나를 썼습니다.

하나를 쓸 때 핵심은 불을 먼저 넣고 사람을 넣어야한다는 점입니다.

이유는 사람을 먼저 넣을 경우 불이 퍼지는 위치임을 알지 못하고 불에 휩싸여 죽을 수가 있기 때문입니다!

BFS탈출 조건은.. 맵의 가장자리에 도착하면 탈출한 것임으로.. 끝나겠죠!?!?!?

#include <cstdio>
#include <iostream>
#include <queue>
#include <vector>
#include <string.h>
#define MAX_SIZE 1000
 
using namespace std;
 
typedef struct
{
    int x;
    int y;
    int sec;
    bool type;
} pos;
 
vector<pair<int, int> > v;//fire_pos
 
bool visit[MAX_SIZE][MAX_SIZE];
char map[MAX_SIZE][MAX_SIZE];
int n, m;
int sx, sy;
 
void input()
{
    scanf("%d %d", &n, &m);
    getchar();
 
    for(int i = 0; i < m; i++)
    {
        for(int j = 0; j < n; j++)
        {
            char c = getchar();
            map[i][j] = c;
            if(c == '*') v.push_back(make_pair(i, j));
            else if(c == '@') sx = i, sy = j;
        }
        getchar();
    }
}
 
int bfs()
{
    queue<pos> q;
 
    for(int i = 0; i < v.size(); i++) q.push(pos{v[i].first, v[i].second, 0, 0});
    q.push(pos{sx, sy, 0, 1});
 
    visit[sx][sy] = 1;
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};
 
    while(!q.empty())
    {
        pos pop_data = q.front();
        q.pop();
 
        int x = pop_data.x;
        int y = pop_data.y;
        int sec = pop_data.sec;
        int type = pop_data.type;
 
        if(type && (x == 0 || x == m - 1|| y == 0 || y == n - 1)) return sec + 1;
 
        for(int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx < 0 || ny < 0 || nx >= m || ny >= n) continue;
            if(map[nx][ny] == '#' || map[nx][ny] == '*') continue;
            if(visit[nx][ny]) continue;
 
            if(type) visit[nx][ny] = 1;
            else map[nx][ny] = '*';
 
            q.push(pos{nx, ny, sec + 1, type});
        }
    }
 
    return 0;
}
 
void print()
{
    for(int i = 0; i < m; i++) printf("%s\n", map[i]);
}
 
int main()
{
    int t;
    scanf("%d", &t);
 
    for(int test_case = 0; test_case < t; test_case++)
    {
        v.clear();
        memset(visit, 0, sizeof(visit));
 
        input();
 
        int ret = bfs();
        if(ret) printf("%d\n", ret);
        else printf("IMPOSSIBLE\n");
    }
 
    return 0;
}