글 읽기 - 왜 틀렸는지 모르겠습니다 고수님들,, 도와주십쇼!

joongh0113 3년 전 1

테스트 케이스 출력은 잘 됩니다. 반례를 찾아 주시면 더 감사하겠습니다.

#include<iostream>
#include<queue>
#include<string>

using namespace std;

int x[4] = { 0, 1, 0, -1 };
int y[4] = { 1, 0, -1, 0 };


#define MX 578912

int main() {
	int N, M; cin >> N >> M;
	vector<vector<bool>>visited(N);
	vector<string>v(N);
	int min_exit = MX;
	for (int i = 0; i < N; ++i) {
		cin >> v[i];
		visited[i].resize(M, false);
	}

	queue<pair<pair<int, int>, pair<int, int>>>q; 
	q.push({ {1, 0}, {0, 0} });
	visited[0][0] = true;
	int cur_x, cur_y, nxt_x, nxt_y;
	int cnt, bw;

	while (!q.empty()) {

		cnt = q.front().first.first; // 나아간 횟수
		bw = q.front().first.second; // 벽을 부술 수 있는지
		cur_x = q.front().second.first; 
		cur_y = q.front().second.second;
		q.pop();
		if (cur_y == N - 1 && cur_x == M - 1) {
			if (min_exit > cnt) min_exit = cnt;
			continue;
		}
		
		for (int i = 0; i < 4; ++i) {
			nxt_x = cur_x + x[i];
			nxt_y = cur_y + y[i];

			if (nxt_x < 0 || nxt_x == M || nxt_y < 0 || nxt_y == N) continue;
			if (visited[nxt_y][nxt_x]) continue;
			if (v[nxt_y][nxt_x] == '1') {
				if (bw) continue;
				else {
					q.push({ {cnt + 1, 1}, {nxt_x, nxt_y} });
					visited[nxt_y][nxt_x] = true;
					continue;
				}
			}
			q.push({ {cnt + 1, bw}, {nxt_x, nxt_y} });
			visited[nxt_y][nxt_x] = true;
			
		}

	}
	if (min_exit == MX) cout << -1;
	else cout << min_exit;
	return 0;
}

palilo 3년 전 5

joongh0113 3년 전 0

BFS에서 큐가 어디를 방문했는지 정보를 각각 가지고 있어야 하나요?

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

문제

문제

출처

ICPC

왜 틀렸는지 모르겠습니다 고수님들,, 도와주십쇼!

joongh0113 3년 전 1

palilo 3년 전 5

joongh0113 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말