[백준 5427] 불

www.acmicpc.net/problem/5427

5427번: 불

 

bfs 응용문제이다.

"불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다. " -> 불이 먼저 이동한다는 말이다.

 

불을 먼저 이동시킨다음에 상근이가 배열을 벗어날 수 있다면 탈출!

#include <iostream>
#include <queue>
#include <string.h>

using namespace std;

int t, w, h;
int src_x, src_y;
char arr[1001][1001];
int person_visited[1001][1001];
int drow[4] = {1, -1, 0, 0};
int dcol[4] = {0, 0, 1, -1};

struct st
{
  int row, col;
  bool fire;
};
queue<st> q;

int BFS(int row, int col);
int main(void)
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);

  cin >> t;

  for (int i = 0; i < t; i++)
  {
    cin >> w >> h;
    memset(person_visited, 0, sizeof(person_visited));
    for (int j = 0; j < h; j++)
    {
      string ws;
      cin >> ws;
      for (int k = 0; k < w; k++)
      {
        arr[j][k] = ws[k];
        if (arr[j][k] == '@')
        {
          src_x = k;
          src_y = j;
        }

        if (arr[j][k] == '*')
        {
          q.push({j, k, true});
        }
      }
    }

    int result = BFS(src_y, src_x);
    if (result == -1)
    {
      cout << "IMPOSSIBLE\n";
    }
    else
    {

      cout << result << "\n";
    }
    while (!q.empty())
    {
      q.pop();
    }
  }
  return 0;
}

bool isValid(int row, int col)
{
  if (row < 0 || col < 0 || row > h - 1 || col > w - 1)
  {
    return false;
  }
  return true;
}

int BFS(int row, int col)
{
  q.push({row, col, false});

  while (!q.empty())
  {
    st front = q.front();
    q.pop();
    if (front.fire)
    {
      for (int i = 0; i < 4; i++)
      {
        int next_row = front.row + drow[i];
        int next_col = front.col + dcol[i];

        if (!isValid(next_row, next_col))
        {
          continue;
        }
        if (arr[next_row][next_col] != '#' && arr[next_row][next_col] != '*')
        {
          arr[next_row][next_col] = '*';
          q.push({next_row, next_col, true});
        }
      }
    }
    else
    {
      for (int i = 0; i < 4; i++)
      {
        int next_row = front.row + drow[i];
        int next_col = front.col + dcol[i];
        if (!isValid(next_row, next_col))
        {
          return person_visited[front.row][front.col] + 1;
        }

        if (arr[next_row][next_col] == '.' &&
            person_visited[next_row][next_col] == 0)
        {
          person_visited[next_row][next_col] = person_visited[front.row][front.col] + 1;
          q.push({next_row, next_col, false});
        }
      }
    }
  }

  return -1;
}