글 읽기 - c++ bfs 7%에서 틀립니다. 고수님들 도와주십셔 ㅠㅠ

dkxm99 2년 전 0

예제나 모든 질문글에 있는 테케가 전부 잘 돌아갑니다. 근데 제출만 하면 꼭 7%에서 계속 틀리네요... 반례 알려주시거나 혹은 어디가 문제인지 지적해주시면 감사하겠습니다.

#include <iostream>
#include <queue>
#include <cstring>
#define INF (987654321)
using namespace std;

char map[1000][1000];
int Fmap[1000][1000];
bool visited[1000][1000];
int dx[4] = { 1, -1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };
int n, m, t;
int mx, my;
queue<pair<int, int>>qf;

void init() //불맵을 최댓값으로 초기화
{
	for (int i = 0; i < 1000; i++) {
		for (int j = 0; j < 1000; j++) {
			Fmap[i][j] = INF;
		}
	}
}

void bfsMan(int b, int a) { // 지훈이 이동 bfs
	queue<pair<pair<int, int>, int>>q;
	visited[b][a] = true;
	q.push(make_pair(make_pair(b, a), 0));
	while (!q.empty()) {
		int y = q.front().first.first;
		int x = q.front().first.second;
		int cnt = q.front().second;
		q.pop();
		if (y == 0 || x == 0 || y == m - 1 || x == n - 1) { //탈출했을경우 결과출력
			cout << cnt + 1;
			return;
		}
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (ny < 0 || nx < 0 || ny >= m || nx >= n) continue;
			if ((map[ny][nx] != '#' && map[ny][nx] != 'F') && !visited[ny][nx]) {
				if (Fmap[ny][nx] > cnt + 1) {
					visited[ny][nx] = true;
					q.push(make_pair(make_pair(ny, nx), cnt + 1));
				}
				else if (Fmap[ny][nx] <= cnt + 1) { //불보다 지훈이가 늦게 도착하거나 동일하게
                      cout << "IMPOSSIBLE";         //도착하여 지훈이가 불타죽은경우
					  return;                              			
				}
			}
		}
	}
}

void bfsFire() { //불 이동 bfs
	while (!qf.empty()) {
		int y = qf.front().first;
		int x = qf.front().second;
		qf.pop();
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (ny < 0 || nx < 0 || ny >= m || nx >= n) continue;
			if (map[ny][nx] != '#') {
				if (Fmap[ny][nx] > Fmap[y][x] + 1) { //조건 만족시 이동할칸에 현재칸 + 1값을 넣어줌
					Fmap[ny][nx] = Fmap[y][x] + 1;
					qf.push(make_pair(ny, nx));
				}
			}
		}
	}
}

int main() {
	cin >> n >> m;
	init();
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
			if (map[i][j] == 'J') {
				mx = j;
				my = i;
			}
			else if (map[i][j] == 'F') {
				qf.push(make_pair(i, j));
				Fmap[i][j] = 0;
			}
		}
	}
	bfsFire();
	bfsMan(my, mx);
	return 0;
}

dps2 2년 전 0

테스트케이스가 잘 돌아간다고 하셨는데

https://wandbox.org/

온라인 컴파일러로 실행시켜보니 예제입력부터 틀리게 나옵니다.

컴파일 환경을 알려주실 수 있나요?

dkxm99 2년 전 0

비주얼스튜디오 사용중입니다. 실제로 예제는 맞게 나오고 7%까지도 정답이 나왔습니다.

또 제가 waterloo 예제들을 돌려보던 도중에

4 6
######
......
#.J###
#F####

이 예제의 출력이 impossible 이 나오는데 정답은 5더군요.

제가 푼 방법은 불을 먼저 확산시킨후에 지훈이를 이동시킬때 +1씩하는 cnt 와 불맵에 들어있는 값을 비교하여 불맵의 값보다 cnt의 값이 적으면 불이 번지지않는걸로 판단하여 이동하는 방식입니다.

dkxm99 2년 전 0

그리고 47번째 줄의 조건문을 없애고 해당 함수 while문 바깥에

cout << "IMPOSSIBLE";
return;

를 해줬더니 통과했습니다.

https://www.acmicpc.net/board/...

여기에있는 반례중에

*4*

5 5
....F
...J#
....#
....#
...#.

이부분을 제가 잘못 이해해서 코드가 계속 틀린거였습니다.

글을보면 위에있는게 정답이고 그 아래가 입력인데

제가 밑에 있는게 정답이고 위에있는게 입력인것으로 착각해서

*4*

5 5
....F
...J#
....#
....#
...#.

이게 아니라

5 5
....F
...J#
....#
....#
...#.

*IMPOSSIBLE*

이걸로 보아서 계속 틀린거였습니다.

결국 통과는 했네요 ㅋㅋ

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

c++ bfs 7%에서 틀립니다. 고수님들 도와주십셔 ㅠㅠ

dkxm99 2년 전 0

dps2 2년 전 0

dkxm99 2년 전 0

dkxm99 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말