5427번 불

문제:

• 문제 링크
  상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다.

매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에는 불이 붙지 않는다. 상근이는 동서남북 인접한 칸으로 이동할 수 있으며, 1초가 걸린다. 상근이는 벽을 통과할 수 없고, 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다. 상근이가 있는 칸에 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다.

빌딩의 지도가 주어졌을 때, 얼마나 빨리 빌딩을 탈출할 수 있는지 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스는 최대 100개이다.

각 테스트 케이스의 첫째 줄에는 빌딩 지도의 너비와 높이 w와 h가 주어진다. (1 ≤ w,h ≤ 1000)

다음 h개 줄에는 w개의 문자, 빌딩의 지도가 주어진다.

• '.': 빈 공간
• '#': 벽
• '@': 상근이의 시작 위치
• '*': 불

각 지도에 @의 개수는 하나이다.

출력:

각 테스트 케이스마다 빌딩을 탈출하는데 가장 빠른 시간을 출력한다. 빌딩을 탈출할 수 없는 경우에는 "IMPOSSIBLE"을 출력한다.

접근 방법

1. 불을 이동 시킨다. ( # 상근이가 이동 한 뒤에 불이 오면 죽어요 )
2. 상근이가 이동할 수 있는 모든 곳을 큐에 넣는다.
3. 가장자리에 도달할 때 까지 반복한다.

코드

접기/펼치기

#include <iostream>
#include <queue>

using namespace std;

int map[1001][1001];
int visit[1001][1001];

int dx[] = { 0, 0 , 1 ,-1};
int dy[] = { 1, -1, 0, 0};

int main()
{
  int t;
  cin >> t;

  while (t--)
  {
    int x, y;
    cin >> x >> y;

    queue<pair<int, int> > sq;
    queue<pair<int, int> > fq;

    for (int i = 0; i < y; i++)
    fill_n(visit[i], x, 0);
    for (int i = 0; i < y; i++)
    {
      string s;
      cin >> s;
      for (int j = 0; j < x; j++)
      {
        map[i][j] = s[j];

        if (map[i][j] == '@')
        {
          sq.push(make_pair(i, j));
        }
        else if (map[i][j] == '*')
          fq.push(make_pair(i, j));
      }
    }
    int count = 0;
    bool escape = false;
    while (!sq.empty() && !escape)
    {
      int fsize = fq.size();
      int ssize = sq.size();



      for(int k = 0 ; k < fsize; k++){
        pair<int, int > fcur = fq.front();
        fq.pop();
        for(int i = 0 ; i < 4 ; i++)
        {
        int ny = fcur.first + dy[i];
        int nx = fcur.second + dx[i];

        if(nx <0 || ny < 0 || nx >= x || ny >= y) continue;
        if(map[ny][nx] != '#'&& map[ny][nx] != '*'){
          fq.push(make_pair(ny, nx));
           map[ny][nx] = '*';
        }
        }
      }

      for(int k = 0 ; k < ssize; k++)
      {

        pair<int, int > scur = sq.front();sq.pop();
        if(scur.first == 0 || scur.second == 0 || scur.first == y-1 || scur.second == x-1)
        {
          escape = true;
          break;
        }
        for(int i = 0 ; i < 4  ; i ++)
        {
          int ny = scur.first + dy[i];
          int nx = scur.second + dx[i];

          if(nx <0 || ny < 0 || nx >= x || ny >= y) continue;
          if(map[ny][nx] == '.' && visit[ny][nx] == 0)
          {
            sq.push(make_pair(ny,nx));
            visit[ny][nx] = 1;
          }
        }
      }
      count ++;
      if(escape) break;
    }
    if(escape)
    cout << count << "\n";
    else cout << "IMPOSSIBLE\n";
  }
}