3주차-4 4179번: 불!

- 불의 이동 경로와 지훈이의 이동 경로 (최단 거리)를 비교해서 지훈이가 탈출이 가능하다면 최단 거리 출력

- 불이 더 빨라서 탈출이 불가능하다면 IMPOSSIBLE을 출력하는 문제

 

/*
	1. 지훈이의 위치, 불이 붙은 위치
	2. 탈출할 수 있다면 얼마나 빨리 탈출할 수 있는지, 탈출할 수 없는지
	3. 지훈이와 불은 벽을 통과할 수 없음
	
	4. 사람은 1명, 불은 여러 개일 수 있음.
*/

/*
	1. BFS -> '#'이면 continue 조건 추가
	2. 사람 queue, 불 queue를 따로 생성
	2-1. 여러 불의 시작 인덱스를 담을 수 있는 vector 컨테이너 생성

	3. 사람이 위치한 좌표값이 '#'이 아니고, BFS 조건이 continue에 걸린다면?
	3-1. 사람 BFS값이 불 BFS값보다 작으면 BFS값을 출력
	3-2. 위의 조건에 만족하지 못하면 "IMPOSSIBLE" 출력
*/

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>

using namespace std;

int R, C;
char arr[1004][1004];
int person_visited[1004][1004], fire_visited[1004][1004];
int dy[] = { -1, 1, 0, 0 };
int dx[] = { 0, 0, -1, 1 };

vector<pair<int, int>> person_vec;
vector<pair<int, int>> fire_vec;

queue<pair<int, int>> person_q;
queue<pair<int, int>> fire_q;

const int INF = 1e8 + 4;

int result;

void Fire_BFS(int y, int x)
{
	while (!fire_q.empty())
	{
		tie(y, x) = fire_q.front();
		fire_q.pop();

		for (int i = 0; i < 4; i++)
		{
			int ny = y + dy[i];
			int nx = x + dx[i];

			if (ny < 0 || ny >= R || nx < 0 || nx >= C || fire_visited[ny][nx] != INF || arr[ny][nx] == '#') continue;

			fire_visited[ny][nx] = fire_visited[y][x] + 1;

			fire_q.push({ ny, nx });
		}
	}
}

void Person_BFS(int y, int x)
{
	while (!person_q.empty())
	{
		tie(y, x) = person_q.front();
		person_q.pop();

		if (y == 0 || y == R - 1 || x == 0 || x == C - 1)
		{
			result = person_visited[y][x];
			break;
		}

		for (int i = 0; i < 4; i++)
		{
			int ny = y + dy[i];
			int nx = x + dx[i];

			if (ny < 0 || ny >= R || nx < 0 || nx >= C || person_visited[ny][nx] || arr[ny][nx] == '#') continue;

			person_visited[ny][nx] = person_visited[y][x] + 1;

			if (person_visited[ny][nx] < fire_visited[ny][nx])
				person_q.push({ ny, nx });
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	fill(&fire_visited[0][0], &fire_visited[0][0] + 1004 * 1004, INF);

	cin >> R >> C;
	for (int i = 0; i < R; i++)
	{
		for (int j = 0; j < C; j++)
		{
			cin >> arr[i][j];

			if (arr[i][j] == 'J')
			{
				person_vec.push_back({ i, j });
				person_q.push({ i, j });
				person_visited[i][j] = 1;
			}

			else if (arr[i][j] == 'F')
			{
				fire_vec.push_back({ i, j });
				fire_q.push({ i, j });
				fire_visited[i][j] = 1;
			}
		}
	}

	for (const auto& v : fire_vec)
	{
		Fire_BFS(v.first, v.second);
	}

	for (const auto& v : person_vec)
	{
		Person_BFS(v.first, v.second);
	}

	if (result == 0) cout << "IMPOSSIBLE" << '\n';
	else cout << result << '\n';

	return 0;
}