[백준] [c++] 4179번 불!

​

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

4179번: 불!

문제 지훈이는 미로에서 일을 한다. 지훈이를 미로에서 탈출하도록 도와주자! 미로에서의 지훈이의 위치와 불이 붙은 위치를 감안해서 지훈이가 불에 타기전에 탈출할 수 있는지의 여부, 그리고 얼마나 빨리 탈출할 수 있는지를 결정해야한다. 

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
int r, c;
char arr[1002][1002];

queue<pair<int,int>> q;//불

int time[1002][1002];

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


int bfs(void) {
	while (!q.empty()) {
		pair<int, int> p;
		p = q.front();
		q.pop();
		/*
		for (int i = 0; i < r; i++) {
			for (int j = 0; j < c; j++) {
				cout << arr[i][j];
			}
			cout << endl;
		}
		cout << endl;
		*/

		if (arr[p.first][p.second] == 'F') {
			for (int i = 0; i < 4; i++) {
				int nx = p.second + dx[i];
				int ny = p.first + dy[i];

				if (0 <= nx && nx < c && 0 <= ny && ny < r) {
					if (arr[ny][nx] == 'J' || arr[ny][nx] == '.') {
						arr[ny][nx] = 'F';
						q.push({ ny,nx });
					}
				}
			}
		}

		else if (arr[p.first][p.second] == 'J') {
			if (p.first == 0 || p.second == 0 || p.second + 1 == c || p.first + 1 == r) {
				return time[p.first][p.second] + 1;
			}

			for (int i = 0; i < 4; i++) {
				int nx = p.second + dx[i];
				int ny = p.first + dy[i];

				if (0 <= nx && nx < c && 0 <= ny && ny < r) {
					if (arr[ny][nx] == '.') {
						arr[ny][nx] = 'J';
						time[ny][nx] = time[p.first][p.second] + 1;
						q.push({ ny,nx });
					}
				}
			}
		}

	}
	return -1;
}


int main() {
	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] == 'F') {
				q.push({ i,j });
			}
			if (arr[i][j] == 'J') {
				q.push({ i,j });
			}
			
			
		}
	}
	
	int result = bfs();

	if (result == -1) {
		cout << "IMPOSSIBLE";
	}
	else {
		cout << result;
	}
}