[백준/BOJ] 백준 1963번 : 소수 경로

https://www.acmicpc.net/problem/1963

1963번: 소수 경로

한자리를 다른 수로 바꿔가며 바꾸려는 소수로 가는 최소 변환 횟수를 구한다

 

코드

#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
#include <cstring>
using namespace std;

int tc;
string a, b;
int not_prime[10000];
int discovered[10000];
int depth[10000];

int Solve(string start, string dest)
{
	discovered[stoi(start)] = 1;
	depth[stoi(start)] = 0;

	queue<string> q;
	q.push(start);

	while (!q.empty())
	{
		string here = q.front();
		q.pop();

		//dest수에 도달 했을때
		if (here == dest)
			return depth[stoi(here)];

		//한자리를 다른 수로 바꾼다
		for (int i = 0; i < 4; i++)
		{
			for (int j = 0; j <= 9; j++)
			{
				string there = here;
				there[i] = (j + '0');

				if (there[0] != '0' && not_prime[stoi(there)] == 0 && discovered[stoi(there)] == 0)
				{
					discovered[stoi(there)] = 1;
					depth[stoi(there)] = depth[stoi(here)] + 1;

					q.push(there);
				}
			}
		}
	}

	return -1;
}

//소수가 아닌수들을 1로 체크한다
void not_primeMake()
{
	memset(not_prime, 0, sizeof(not_prime));

	not_prime[0] = 1;
	not_prime[1] = 1;

	for (int i = 2; i < 10000; i++)
	{
		if (not_prime[i] == 0)
		{
			for (int j = i * 2; j < 10000; j = j + i)
				not_prime[j] = 1;
		}
	}
}

void Pre()
{
	memset(discovered, 0, sizeof(discovered));
	memset(depth, 0, sizeof(depth));
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	not_primeMake();

	int result;

	cin >> tc;

	for (int t = 0; t < tc; t++)
	{
		Pre();

		cin >> a >> b;

		result = Solve(a, b);

		if (result == -1)
			cout << "Impossible" << "\n";
		else
			cout << result << "\n";
	}

	return 0;
}