[BOJ]伯俊4179号火!

リンク

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

質問する

志訓は迷宮で働いている.智勲を助けて迷宮を脱出せよ!
智勲の迷路での位置と点火された位置を考慮して、智勲が火に焼かれる前に脱出できるかどうか、そしてどれだけ速いスピードで脱出できるかを決めなければならない.
智勲と火は毎分水平または垂直に1格移動する(傾斜せずに移動する).
火は各点から4方向に拡散する.
ジフンは迷宮の端に近い空間から脱出できる.
智勲と火は壁のある空間を通ることができない.

入力

入力された最初の行には、スペースで区切られた2つの整数RとCが与えられます.ただし,1≦R,C≦1000であった.Rは迷宮行の個数,Cは列の個数である.
次の入力では、R行にそれぞれ迷路行が与えられる.
各文字の意味は次のとおりです.
#:壁
.:通過可能な空間
J:ジフンの迷宮での初期位置(通過可能な空間)
F:発火する空間
Jは入力に1つだけ与えられる.

しゅつりょく

智勲が火が到着するまで迷宮を脱出できなければ、IMPOSIBLEを出力する.
智勲が迷宮から脱出できれば、最も速い脱出時間を出力する.

に答える

 #include <iostream>
#include <string>
#include <stack>
#include <queue>
#define X first
#define Y second 
using namespace std;
int r, c;
string board[1001];
int dist1[1001][1001]; //불의 전파 시간
int dist2[1001][1001]; //J의 이동시간
int dx[4] = { 0, 1, 0, -1 };
int dy[4] = { 1, 0, -1, 0 };

int main(void) {
	//먼저 불이 지나가는 bfs 구하고 J가 가는 길 bfs를 구한다.
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> r >> c;
	for (int i = 0; i < r; i++) { //모든 dist -1로 초기화
		fill(dist1[i], dist1[i] + c, -1);
		fill(dist2[i], dist2[i] + c, -1);
	}
	for (int i = 0; i < r; i++) {
		cin >> board[i];
	}

	queue <pair<int, int>> q1;
	queue <pair<int, int>> q2;
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			if (board[i][j] == 'F') { //불을 먼저 푸시
				q1.push({ i, j });
				dist1[i][j] = 0;
			}
			if (board[i][j] == 'J') { //불을 먼저 푸시
				q2.push({ i, j });
				dist2[i][j] = 0;
			}
		}
	}
		//불에 대한 bfs
		while (!q1.empty()) {
			pair <int, int > cur = q1.front();
			q1.pop();
			for (int dir = 0; dir < 4; dir++) {
				int nx = cur.X + dx[dir];
				int ny = cur.Y + dy[dir];
				if (nx < 0 || nx >= r || ny < 0 || ny >= c) continue;
				if (dist1[nx][ny] >= 0 || board[nx][ny] == '#') continue;
				dist1[nx][ny] = dist1[cur.X][cur.Y] + 1;
				q1.push({ nx, ny });
			}
		}
	
		//J에 대한 bfs
		while (!q2.empty()) {
			pair <int, int> cur = q2.front();
			q2.pop();
			for (int dir = 0; dir < 4; dir++) {
				int nx = cur.X + dx[dir];
				int ny = cur.Y + dy[dir];
				if (nx < 0 || nx >= r || ny <0 || ny >= c) { // 범위를 넘긴다는 것은 곧 탈출에 성공했다는 의미. 큐에 반드시 거리순으로 들어가므로 최초에 탈출한 시간을 입력하면 됨. 
					cout << dist2[cur.X][cur.Y] + 1;
					return 0;
				}
				if (dist2[nx][ny] >= 0 || board[nx][ny] == '#') continue;
				if (dist1[nx][ny] != -1 && dist1[nx][ny] <= dist2[cur.X][cur.Y] + 1) continue;
				//해당 칸에 J가 가는 최소 시간이 불길이 닿는 시간보다 같거나 크면 해당 칸에 갈 수 없다. 불의 전파 시간을 조건에 추가.
				dist2[nx][ny] = dist2[cur.X][cur.Y] + 1;
				q2.push({ nx, ny });
			}
		}
		cout << "IMPOSSIBLE"; // 여기에 도달했다는 것은 탈출에 실패를 의미. 
	
}

説明:

👨🏻‍🏫 対火のbfsと対智勲のbfsは別々に解決できる.まずbfsによる火の伝搬を迂回し,各格子における火の伝搬時間を事前に求めた.そして智勲はbfsを求め、Jが行く最小時間が炎が到着する時間以上であれば、この格子に行くことはできない.火の伝播時間を条件に加えなければならない.
これまでbfsの目的地が決まっていたり、他に行く場所がなかったりしたとき、ずっと回っていたのに対して、今回は外郭に逃げます.範囲を超えたのは、すぐに脱出に成功したことを意味します.キューは距離順に入る必要があるので、最初に脱出した時間を入力して戻ります.
📌 智勲は火の影響を受けているが、火の伝播は智勲の影響を受けないので、まず不満を伝播させることは可能だ.しかし,Bが相互に影響する場合,どちらか一方を最後まで伝播することは不可能である.AとBを時間順に同時に行います.