백준4179: 불!

불! 성공다국어

한국어   

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

256 MB

22274

5303

3615

21.918%

문제

지훈이는 미로에서 일을 한다. 지훈이를 미로에서 탈출하도록 도와주자!

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

지훈이와 불은 매 분마다 한칸씩 수평또는 수직으로(비스듬하게 이동하지 않는다)  이동한다. 

불은 각 지점에서 네 방향으로 확산된다. 

지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다. 

지훈이와 불은 벽이 있는 공간은 통과하지 못한다.

입력

입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다.

다음 입력으로 R줄동안 각각의 미로 행이 주어진다.

 각각의 문자들은 다음을 뜻한다.

• #: 벽
• .: 지나갈 수 있는 공간
• J: 지훈이의 미로에서의 초기위치 (지나갈 수 있는 공간)
• F: 불이 난 공간

J는 입력에서 하나만 주어진다.

출력

지훈이가 불이 도달하기 전에 미로를 탈출 할 수 없는 경우 IMPOSSIBLE 을 출력한다.

지훈이가 미로를 탈출할 수 있는 경우에는 가장 빠른 탈출시간을 출력한다. 

예제 입력 1 복사

4 4
####
#JF#
#..#
#..#

예제 출력 1 복사

3

#include <iostream>
#include<queue>
#include<vector>
using namespace std;
int r, c;
char Map[1001][1001];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
bool visited[1001][1001];
int Jx, Jy;
vector<pair<int, int>> Fire;
int answer = 0;
void bfs() {
	queue<pair<int, int>>J;
	queue<pair<int, int>>F;
	J.push({ Jy,Jx });
	visited[Jy][Jx] = true;
	for (int i = 0; i < Fire.size(); i++) {
		F.push({ Fire[i].first,Fire[i].second });
	}
	int round = 0;
	while (!J.empty()) {

		int size = F.size();
		for (int i = 0; i < size; i++) {
			int y = F.front().first;
			int x = F.front().second;
			F.pop();

			for (int i = 0; i < 4; i++) {
				int ny = y + dy[i];
				int nx = x + dx[i];
				if (ny > r || ny<1 || nx >c || nx < 1)continue;
				if (Map[ny][nx] == '#' || Map[ny][nx] == 'F')continue;
				Map[ny][nx] = 'F';
				F.push({ ny,nx });
			}
		}
		size = J.size();
		for (int i = 0; i < size; i++) {
			int y = J.front().first;
			int x = J.front().second;
			J.pop();

			for (int i = 0; i < 4; i++) {
				int ny = y + dy[i];
				int nx = x + dx[i];
				if (visited[ny][nx] == true)continue;
				if (Map[ny][nx] == '#' || Map[ny][nx] == 'F')continue;
				if (ny > r || ny<1 || nx >c || nx < 1) {
					answer = round + 1;
					return;
				}
				visited[ny][nx] = true;
				J.push({ ny,nx });
			}
		}
		round++;
	}
}

int main() {
	cin >> r >> c;
	for (int i = 1; i <= r; i++) {
		for (int j = 1; j <= c; j++) {
			cin >> Map[i][j];
			if (Map[i][j] == 'J') {
				Jy = i, Jx = j;
			}
			if (Map[i][j] == 'F') {
				Fire.push_back({ i,j });
			}
		}
	}
	bfs();
	if (answer == 0)
		cout << "IMPOSSIBLE" << '\n';
	else 
		cout << answer;

	return 0;
}

정답률이 낮아서 좀 쫄았는데, 그렇게 어렵지 않았던 문제이다!

특별히 고려할 점은 불이 여러곳에서 동시에 나면서 시작할 수 있다는 것이다.