백준 1963번 C++

#include <iostream>
#include <math.h>
#include <queue>
#include <cstring>
#include <string>

using namespace std;
const int MAX = 10000;
int prime[MAX];
int visited[MAX];
char increase[10] = { '0','1','2','3','4','5', '6','7','8','9' };

void calprime() {
	for (int i = 1000; i < 10000; i++) {
		int num = (int)sqrt(i);
		for (int j = 2; j <= num; j++) {
			if (i%j == 0) {
				prime[i] = -1;
				break;
			}
		}
	}
}

int bfs(string i, string j) {
	queue<pair<string,int>> q;
	q.push(make_pair(i,0));
	visited[atoi(i.c_str())] = 1;

	while (!q.empty()) {
		string current = q.front().first;
		int count = q.front().second;
		q.pop();

		if (current == j)
			return count;

		for (int k = 0; k < 4; k++) {
			for (int index = 0; index < 10; index++) {
				string change = current;
				change[k] = increase[index];
				int changenum = atoi(change.c_str());
				if (prime[changenum] == 0 && visited[changenum] == -1 && change[0] != '0') {
					q.push(make_pair(change, count + 1));
					visited[changenum] = 1;
				}
			}
		}
	}
	return -1;
}

int main(void) {
	int testcase;
	string first, second;
	
	cin >> testcase;
	memset(prime, 0,sizeof(prime));
	calprime();
	for (int i = 0; i < testcase; i++) {
		cin >> first >> second;
		memset(visited, -1, sizeof(visited));
		int answer = bfs(first,second);
		if (answer == -1)
			cout << "Impossible" << endl;
		else
			cout << answer << endl;
	}
	return 0;
}