글 읽기 - 4179. 불! 질문있습니다.

minjae200 5년 전 0

J 위치 queue와 F위치 queue를사용하여 우선 J가이동할 수있는 위치를 BFS돌렸고 불을 퍼트렸습니다(BFS) 그리고 범위에 벗어나는지점이 있으면 탈출에 성공한것이므로 ans++를하여 결과를 출력해주는 형식으로 시도하였습니다.

57프로에서 틀렸습니다. 뜨는데 혹시 예외케이스나 잘못된점이 있나요

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

int R, C;
char maze[1000][1000];
bool visited[1000][1000];
int ans;
int dx[4] = { 0,0,-1,1 };
int dy[4] = { -1,1,0,0 };
queue<pair<int, int>> Jq;
queue<pair<int, int>> Fq;

bool CheckRange(int y, int x) {
	if (0 <= y && y < R && 0 <= x && x < C) return true;
	else return false;
}

bool BFS(void) {
	while (!Jq.empty()) {
		int jq_size = Jq.size();
		int fq_size = Fq.size();
		while (jq_size--) {
			int cur_jx = Jq.front().second;
			int cur_jy = Jq.front().first;
			Jq.pop();
			for (int i = 0; i < 4; i++) {
				int next_jx = cur_jx + dx[i];
				int next_jy = cur_jy + dy[i];
				if (CheckRange(next_jy, next_jx)) {
					if (!visited[next_jy][next_jx] && maze[next_jy][next_jx] == '.') {
						visited[next_jy][next_jx] = true;
						Jq.push(make_pair(next_jy, next_jx));
					}
				}
				else { ans++;  return true; }
			}
		}
		ans++;
		//불퍼트리기
		while (fq_size--) {
			int cur_fx = Fq.front().second;
			int cur_fy = Fq.front().first;
			Fq.pop();
			for (int i = 0; i < 4; i++) {
				int next_fx = cur_fx + dx[i];
				int next_fy = cur_fy + dy[i];
				if (CheckRange(next_fy, next_fx) && maze[next_fy][next_fx] != '#' && maze[next_fy][next_fx] != 'F') {
					Fq.push(make_pair(next_fy, next_fx));
					maze[next_fy][next_fx] = 'F';
				}
			}
		}
		/*for (int i = 0; i < R; i++)
		{
			for (int j = 0; j < C; j++)
				cout << maze[i][j];
			cout << endl;
		}*/
	}
	return false;
}

int main(void)
{
	cin >> R >> C;
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			cin >> maze[i][j];
			if (maze[i][j] == 'J') {
				Jq.push(make_pair(i, j));
				visited[i][j] = true;
			}
			if (maze[i][j] == 'F') {
				Fq.push(make_pair(i, j));
			}
		}
	}

	if (BFS()) {
		cout << ans << endl;
	}
	else cout << "IMPOSSIBLE" << endl;

//	int A; cin >> A;
	return 0;
}