[백준 4179] 불!

www.acmicpc.net/problem/4179

4179번: 불!

 

이전에 풀었던 문제와 유사하다. 불과 지훈이가 동시에 움직일 때 지훈이는 건물밖으로 벗어나면 탈출하는 문제이다.

 

불이 먼저 움직여야 정확한 결과가 나온다.

따라서 불의 시작 위치를 푸쉬하고 지훈이의 위치는 나중에 푸쉬한다.

 

불의 경우 미로 내에서 .이거나 J이면 이동한다. 이동후에는 미로에 F 표시를 한다.

지훈이는 미로내에서 .이면 이동가능하다. 

 

주의할 점은 q.front에서 건물밖인지 판단하는 건 불가능하다. 왜냐면 for문을 돌면서 miro와 visited에서 범위를 벗어낫기 때문

#include <stdio.h>
#include <queue>

using namespace std;

int r, c, sr, sc;
char miro[1000][1000];
int visited[1000][1000];
int drow[4] = {1, -1, 0, 0};
int dcol[4] = {0, 0, -1, 1};

struct S
{
  int x, y;
  bool fire;
};
queue<S> q;

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

  return true;
}

int bfs()
{
  q.push({sr, sc, false});
  visited[sr][sc] = 1;
  while (!q.empty())
  {
    S fr = q.front();

    q.pop();

    if (fr.fire == true)
    {
      for (int i = 0; i < 4; i++)
      {
        int nextR = fr.x + drow[i];
        int nextC = fr.y + dcol[i];

        if (isValid(nextR, nextC) && (miro[nextR][nextC] == '.' || miro[nextR][nextC] == 'J'))
        {
          q.push({nextR, nextC, true});
          miro[nextR][nextC] = 'F';
        }
      }
    }
    else
    {
      for (int i = 0; i < 4; i++)
      {
        int nextR = fr.x + drow[i];
        int nextC = fr.y + dcol[i];

        if (!isValid(nextR, nextC))
        {
          return visited[fr.x][fr.y];
        }

        if (isValid(nextR, nextC) && miro[nextR][nextC] == '.' && visited[nextR][nextC] == 0)
        {
          q.push({nextR, nextC, false});
          visited[nextR][nextC] = visited[fr.x][fr.y] + 1;
        }
      }
    }
  }
  return -1;
}

int main(void)
{
  scanf("%d %d", &r, &c);

  for (int i = 0; i < r; i++)
  {
    scanf("%s", miro[i]);
    for (int j = 0; j < c; j++)
    {
      if (miro[i][j] == 'F')
      {
        q.push({i, j, true});
      }

      if (miro[i][j] == 'J')
      {
        sr = i;
        sc = j;
      }
    }
  }

  int result = bfs();

  if (result == -1)
  {
    printf("IMPOSSIBLE\n");
  }
  else
  {
    printf("%d\n", result);
  }

  return 0;
}