불! (feat. 백준, 4179번)

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

4179번: 불!

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <string.h>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
int R, C, dx[4], dy[4];
char arr[1002][1002];
bool visit[1002][1002];
int ans[1002][1002];
vector<pair<int, int>> fires;
int bfs(register int x, register int y) {
	memset(visit, false, sizeof(visit));
	queue<pair<int, int>> q;
	for (auto& fire : fires) {
		q.push(fire);
		visit[fire.first][fire.second] = true;
		ans[fire.first][fire.second] = -1;
	}
	q.push(make_pair(x, y));
	visit[x][y] = true;
	ans[x][y] = 1;
	if (x == 1 || x == R || y == 1 || y == C)
		return ans[x][y];
	while (!q.empty()) {
		auto p = q.front(); q.pop();
		x = p.first, y = p.second;
		for (register int d = 0, nx, ny; d < 4; ++d) {
			nx = x + dx[d], ny = y + dy[d];
			if (1 <= nx && nx <= R && 1 <= ny && ny <= C && !visit[nx][ny] && arr[nx][ny] != '#') {
				visit[nx][ny] = true;
				ans[nx][ny] = ans[x][y];
				if (ans[nx][ny] != -1)
					ans[nx][ny] += 1;
				if ((nx == 1 || nx == R || ny == 1 || ny == C) && (ans[nx][ny] != -1))
					return ans[nx][ny];
				q.push(make_pair(nx, ny));
			}
		}
	}
	return -1;
}
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	dx[0] = 1, dx[1] = -1, dx[2] = dx[3] = 0;
	dy[0] = dy[1] = 0, dy[2] = 1, dy[3] = -1;
	memset(arr, 0, sizeof(arr));
	cin >> R >> C;
	register int jx, jy, fx = -1, fy = -1;
	for (register int r = 1, c; r <= R; ++r)
		for (c = 1; c <= C; ++c) {
			cin >> arr[r][c];
			if (arr[r][c] == 'J')
				jx = r, jy = c;
			else if (arr[r][c] == 'F')
				fires.push_back(make_pair(r, c));
		}
	auto ans(bfs(jx, jy));
	if (ans > 0)
		cout << ans;
	else
		cout << "IMPOSSIBLE";
	return 0;
}
// *&)*@*

 

 

문제는 아래와 같은 조건이 누락되어 있습니다. 해당 조건만 인지하신다면 쉽게 풀 수 있습니다.

1. 불은 없거나 하나 이상일 수 있습니다.
2. 지훈이의 시작지점이 탈출구일 수 있습니다.
3. 지훈이보다 불이 먼저 이동해야 합니다.