글 읽기 - 1194번 달이 차오른다, 가자. 문제

kks227 8년 전 0

6종류 열쇠 비트마스킹 + BFS로 돌리는데, 도저히 왜 틀렸는지 모르겠네요.

지인에게 도움을 요청했더니, 비트마스킹 + BFS로 답을 맞추셨다고 하는데 코드를 봐도 차이를 잘 모르겠습니다.

이 문제에 어떤 함정이라던가 주의점이라도 있는지...

#include <cstdio>
#include <cctype>
#include <queue>
using namespace std;

const int roff[4] = {-1, 1, 0, 0};
const int coff[4] = {0, 0, -1, 1};

int main(){
	int N, M;
	char map[50][50];
	int sr, sc, er, ec;
	scanf("%d %d", &N, &M);
	for(int i=0; i<N; i++){
		getchar();
		for(int j=0; j<M; j++){
			map[i][j] = getchar();
			if(map[i][j] == '0'){
				sr = i;
				sc = j;
			}
			else if(map[i][j] == '1'){
				er = i;
				ec = j;
			}
		}
	}

	bool visited[64][50][50] = {0};
	visited[0][sr][sc] = true;
	queue<int> Q;
	Q.push(sr*M + sc);
	int result = 0;
	bool success = false;

	while(!Q.empty()){
		int qSize = Q.size();

		for(int i=0; i<qSize; i++){
			int key = Q.front() / (N*M);
			int r = Q.front() % (N*M) / M;
			int c = Q.front() % M;
			Q.pop();
			if(r==er && c==ec){
				success = true;
				break;
			}

			for(int d=0; d<4; d++){
				int nkey = key;
				int nr = r + roff[d];
				int nc = c + coff[d];
				if(nr<0 || nr>=N || nc<0 || nc>=M) continue;
				if(visited[nkey][nr][nc]) continue;

				if(map[nr][nc] == '#') continue;
				else if(islower(map[nr][nc])) nkey |= (1 << (map[nr][nc]-'a'));
				else if(isupper(map[nr][nc]))
					if( !(nkey & (1 << (map[nr][nc]-'A'))) ) continue;
				visited[nkey][nr][nc] = true;
				Q.push(nkey*N*M + nr*M + nc);
			}
		}

		if(success) break;
		result++;
	}

	if(success) printf("%d\n", result);
	else puts("-1");
}

yukariko 8년 전 1

테스트해본 결과 도착지점이 여러개인 케이스가 존재하는것 같습니다.

재채점이 필요한 시점이네요.

그런데 visit 검사를 nkey 갱신 뒤에 해야 맞는것 아닌가요?

                if(visited[nkey][nr][nc]) continue;
 
                if(map[nr][nc] == '#') continue;
                else if(islower(map[nr][nc])) nkey |= (1 << (map[nr][nc]-'a'));

kks227 8년 전 0

지인분의 도움으로, N이나 M이 1일 때 해시 과정에서 문제가 생길 수 있음을 알았습니다.

하지만 해시를 하지 않아도 여전히 문제가 발생하네요.

또한 visited 방문 여부의 순서가 이상해서 그것도 고쳤지만 여전히 안됩니다.

kks227 8년 전 0

아, yukariko님 제가 마침 지금 visited 검사 순서를 바꿨는데 우연이군요 ㅋㅋㅋㅋㅋ

도움 주셔서 감사합니다.

그나저나 도착점이 여러 개라니... ㅎㄷㄷ 문제가 틀린 것이군요. 한번 테스트해 보겠습니다.

kks227 8년 전 1

yukariko님 감사합니다. 설마 문제 설명이 틀렸으리라고는 생각도 못 했네요...

덕분에 맞췄습니다.

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

문제

문제

출처

ICPC

1194번 달이 차오른다, 가자. 문제

kks227 8년 전 0

yukariko 8년 전 1

kks227 8년 전 0

kks227 8년 전 0

kks227 8년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말