글 읽기 - 소수 경로 질문

krenerd 5년 전 1

1033 8179

의 실행에서 3733=>3739의 변경을 하지 못하고 있습니다.

일의 자리가 바뀌는 다른 예시(1031,1033)은 잘 처리하는데 왜 위의 예시를 변경하지 못하는 것일까요?

고수분들의 도움 부탁드립니다...

get_cpy함수는 (1234,1)을 넣을 시 1230, (1234,2)=>1204, (1234,3)=>1034 와 같이 mode 번째 자리수를 0으로 바꾸ㅓ줍니다.

#include<iostream>
#include<queue>
using namespace std;
int get_cpy(int num, int mode);
bool prime[10000] = {};//true=>소수
int bfs(int stt, int end) {
	queue<int>q;
	int visit[10000];
	for (int i = 1000; i <= 9999; i++)
		visit[i] = -1;
	visit[stt] = 0;
	q.push(stt);
	while (!q.empty()) {
		int digit = 1;
		int num = q.front(),cpy;
		if (num == 3739)cout << '%';
		if (num == end)return visit[end];
		for (int m = 1; m <= 4; m++) {
			cpy = get_cpy(num, m);
			for (int i = 0; i < 9; i++) {
				if (prime[cpy] && visit[cpy] == -1 && cpy > 999) {
					q.push(cpy); visit[cpy] = visit[num] + 1;
				}
				cpy+=digit;
			}
			digit *= 10;
		}
		q.pop();
	}
	return -1;
}
int get_cpy(int num,int mode) {
	switch (mode)
	{
	case 1:
		return (num / 10) * 10;
	case 2:
		return (num / 100) * 100 + num % 10;
	case 3:
		return (num / 1000) * 1000 + num % 100;
	case 4:
		return num % 1000;
	}
}
void check_prime() {
	for (int i = 2; i <= 9999; i++)prime[i] = true;
	for (int i = 2; i*i <= 9999;i++)
		if (prime[i] == true)
			for (int j = 2; i*j <= 9999; j++)
				prime[i*j] = false;
}
int main()
{
	check_prime();
	int t;
	cin >> t;
	while (t--) {
		int a, b;
		cin >> a >> b;
		if (prime[a] == false || prime[b] == false) {
			cout << "Impossible" << '\n';
			return 0;
		}
		a = bfs(a, b);
		if (a == -1)
			cout<<"Impossible" << '\n';
		else cout << a<<'\n';
	}
}

betain24 5년 전 2

i < 9 까지밖에 안되서 3738까지밖에 안됩니다..

            cpy = get_cpy(num, m);
			for (int i = 0; i < 9; i++) {
				if (prime[cpy] && visit[cpy] == -1 && cpy > 999) {
					q.push(cpy); visit[cpy] = visit[num] + 1;
				}
				cpy+=digit;
			}

krenerd 5년 전 0

답변 정말 너무너무너무 감사합니다 ㅠㅠ

간단한 실수를 했네요

이런 사소한 실수를 만들어서... 죄송합니다

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

문제

문제

출처

ICPC

소수 경로 질문

krenerd 5년 전 1

betain24 5년 전 2

krenerd 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말