글 읽기 - 반례좀 찾아주실분 ㅠㅠ

simsimjae 5년 전 0

bfs() 정석대로 문제 풀었는데 어디가 틀렸을까요?

#include <iostream>
#include <algorithm>
#include <math.h>
#include <deque>
#include <memory.h>
using namespace std;
int input1,input2;
bool check[10001];
bool visited[10001];

typedef struct couple {
	int number;
	int depth;
}couple;

deque<couple> que;


couple make_couple(int number, int depth) {
	couple couple;
	couple.number = number;
	couple.depth = depth;
	return couple;
}

void eratos() {
	memset(check, 1, sizeof(check));
	for (int i = 2; i <= 10000; i++) {
		if (check[i])
			for (int j = i * 2; j <= 10000; j += i)
				check[j] = false;
	}
	
	
}

void parse(deque<int>& here,int a) {
	while (a != 0) {
		here.push_front(a % 10);
		a /= 10;
	}
}

int toInt(deque<int>& deq) {
	return deq[0] * 1000 + deq[1] * 100 + deq[2] * 10 + deq[3];
}


int bfs() {
	int result = -1;
	que.push_back(make_couple(input1,0));
	visited[input1] = true;
	while (!que.empty()) {
		int number = que.front().number; 
		int depth = que.front().depth;
		que.pop_front();
		if (number == input2) {
			return depth;
		}
		
		deque<int> temp;
		for (int i = 0; i < 4; i++) {
			temp.clear();
			parse(temp, number);//1033 -> 1/0/3/3
			for (int j = 0; j <= 9; j++) {
				if (i == 0 && j == 0) continue;

				temp[i] = j; // 1 0 3 3 <- 0 ~ 9 
				int currentNum = toInt(temp);
				if (visited[currentNum] == 0 && check[currentNum] == 1) { //그 숫자가 나온적이 없고 그 숫자가 소수인경우 bfs 더 진행
					visited[currentNum] = true;
					que.push_back(make_couple(currentNum, depth + 1));
				}

			}
		}
	}

}

int main() {
	int n;
	cin >> n;
	eratos();
	for(int i = 0; i < n; i++) {
		cin >> input1 >> input2;
		memset(visited, 0, sizeof(visited));
		int result = bfs();
		if (result == -1)
			cout << "Impossible" << endl;
		else
			cout << result << endl;
	}
	return 0;
}

djm03178 5년 전 0

que가 테스트 케이스마다 초기화되지 않았습니다.

그리고 이 문제의 경우 실제로 Impossible을 출력해야 하는 경우가 없는 듯 해서 정답을 받긴 하지만, bfs가 아무것도 찾지 못했을 때 -1을 반환하는 부분이 없습니다.

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

문제

문제

출처

ICPC

반례좀 찾아주실분 ㅠㅠ

simsimjae 5년 전 0

djm03178 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말