글 읽기 - 1963번 소수경로 문제 틀린 이유를 모르겠습니다

hyein96 5년 전 0

예시 케이스는 다 맞는데 틀렸다고 뜨네요 왜 틀렸는지 이유를 전혀 모르겠습니다ㅜ

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <queue>
using namespace std;

bool prime[10001];
int dist[10000];
bool visit[10001];
int num[4];

int main() {

	for (int i = 2; i < 10000; i++) {
		if (prime[i] == true) continue;
		for (int j = i+i; j < 10000; j+=i) {
			prime[j] = true;
		}
	}
	int t;
	scanf("%d", &t);
	while (t--) {
		int a, b;
		scanf("%d %d", &a, &b);
		if (a == b) {
			printf("0\n");
			continue;
		}

		queue<int> q;
		q.push(a);
		visit[a] = true;

		while (!q.empty()) {
			int now = q.front();
			q.pop();

			int front = now;
			for (int i = 0; now != 0; i++) {
				num[i]=now%10;
				now /= 10;
			}

			for (int i = 0; i < 4; i++) {
				for (int j = 0; j < 10; j++) {
					int x = num[i];
					if (i != 3 | j != 0) num[i] = j;
					int n = num[0] + num[1] * 10 + num[2] * 100 + num[3] * 1000;
					if (visit[n] == false && prime[n] == false) {
						q.push(n);
						visit[n] = true;
						dist[n] = dist[front] + 1;
					}
					num[i] = x;
				}
			}

		}
		
		if (dist[b] == 0) {
			printf("Impossible\n");
		}
		else {
			printf("%d\n", dist[b]);
		
		}
		
		
	}

	return 0;
}

pinebananais 5년 전 0

혹시 visit 배열의 초기화를 하지 않음으로서 다음 테스트케이스에 대해 한 번 true가 되었던 값에 참조할 수 없어서 문제가 생기는 건 아닐까요?

hyein96 5년 전 0

전역함수는 자동으로 false로 초기화돼요! 그리고 혹시나 해서 초기화시켜서 돌려봤는데 틀렸다고 뜨네요ㅠㅠ

djm03178 5년 전 0

그 초기화가 아니라, 매 케이스마다의 초기화를 말씀하신 것입니다. 이전 케이스에서 방문한 수를 다음 케이스에서 또 방문할 수 있어야 합니다.

hyein96 5년 전 1

아 제가 완전 멍청했네요ㅠㅠㅠ 두 분 답변 정말정말 감사드립니다!!!ㅠㅠ

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

문제

문제

출처

ICPC

1963번 소수경로 문제 틀린 이유를 모르겠습니다

hyein96 5년 전 0

pinebananais 5년 전 0

hyein96 5년 전 0

djm03178 5년 전 0

hyein96 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말