글 읽기 - c++ bfs 3%에서 틀립니다. 혹시 반례가 또 있을까요?

dkxm99 3년 전 0

5 6

1 1

5 6

0 1 1 1 0 0

0 1 1 0 1 0

0 1 0 0 1 0

0 1 0 1 1 0

답: -1 로 잘나옵니다.

5 6
1 1
5 6

0 1 1 1 0 0
0 1 1 0 0 0
0 1 0 0 1 0
0 1 0 0 1 0
0 1 0 0 0 0

답: 9 로 마찬가지로 잘 나옵니다.

예제 또한 통과했고요.

도대체 뭐가문제길래 3%에서 컷당하는지 모르겠습니다.

#include <iostream>
#include <queue>
#define MAX (1000 + 5)

using namespace std;

int map[MAX][MAX];
bool visited[MAX][MAX];
int dx[4] = { 1, -1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };
int m, n, sy, sx, ey, ex;

int bfs() {
	queue<pair<pair<int, int>, pair<int, bool>>>q;
	visited[sy - 1][sx - 1] = true;
	q.push(make_pair(make_pair(sy - 1, sx - 1), make_pair(0, 0)));
	while (!q.empty()) {
		int y = q.front().first.first;
		int x = q.front().first.second;
		int cnt = q.front().second.first;
		bool wall = q.front().second.second;
		q.pop();
		if (y == ey - 1 && x == ex - 1) {
			return cnt;
		}
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
			if (map[ny][nx] == 0 && !visited[ny][nx]) {
				visited[ny][nx] = true;
				q.push(make_pair(make_pair(ny, nx), make_pair(cnt + 1, wall)));
			}
			else if (map[y][x] == 0 && map[ny][nx] == 1 && !visited[ny][nx]) {
				if (wall == false) {
					visited[ny][nx] = true;
					q.push(make_pair(make_pair(ny, nx), make_pair(cnt + 1, !wall)));
				}
			}
		}
	}
	return -1;
}

int main() {
	cin >> m >> n >> sy >> sx >> ey >> ex;
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
		}
	}
	cout << bfs();
}

dps2 3년 전 2

반례는 다음과 같습니다.

5 2
1 1
5 1
0 0
1 0
0 0
1 1
0 1

지도를 보면

0 0

1 0

0 0

1 1

0 1

에서 좌측 최상단에서 좌측 최하단으로 갈때 위에서 2번째 줄에 있는 벽을 지우는 것이 아니라 아래에서 2번째 벽을 지워야하는데

현재 코드는 벽 1을 통과하여 (3,1)을 먼저 벽 지울 찬스를 써서 도달한 후 visited가 set되어서 0만 밟고 온 path를 막아버립니다.

dkxm99 3년 전 0

답변 감사합니다. visited 배열에 wall 을 하나 추가하여 구분해서 통과했습니다.

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

문제

문제

출처

ICPC

c++ bfs 3%에서 틀립니다. 혹시 반례가 또 있을까요?

dkxm99 3년 전 0

dps2 3년 전 2

dkxm99 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말