Posted in BFS, Kuangbin

POJ 3126 Prime Path/ kuangbin 1F

12/23/2017
Problem: http://poj.org/problem?id=3126
Solution: BFS.

#include<iostream>
#include<queue>
#include<string.h> 
using namespace std;
int mp[10000];

struct node {
	int num, cnt;
	node(int numm, int cntt) {
		num = numm;
		cnt = cntt;
	}
};

queue<node> q;

bool prime(int n) {
	for (int i = 2; i * i <= n; i++) {
		if (n % i == 0) {
			return false;
		}
	}
	return true;
} 

void digit(node n) {
	int div = 0, rem = 0;
	int tmp = 1;	
	for (int i = 1; i <= 3; i++) {
		tmp *= 10;
		div = n.num / tmp;
		rem = n.num % (tmp / 10);
		for (int j = 0; j <= 9; j++) {
			int newNum = div * tmp + j * (tmp / 10) + rem;
			// cout << newNum << endl; 
			if (prime(newNum) && !mp[newNum]) {
				// cout << newNum << endl;
				q.push(node(newNum, n.cnt + 1)); 
				mp[newNum] = 1;
			} 
		}
	}
	rem = n.num % 1000;
	for (int j = 1; j <= 9; j++) {
		int newNum = j * 1000 + rem;
		if (prime(newNum) && !mp[newNum]) {
			// cout << newNum << endl; 
			q.push(node(newNum, n.cnt + 1));
			mp[newNum] = 1;
		}
	}
}

int main() {
	int n;
	cin >> n;
	while (n--) {
		int start = 0, end = 0;
		cin >> start >> end;
		memset(mp, 0, sizeof(mp));
		while (!q.empty()) {
			q.pop();
		}
		node head = node(start, 0);
		mp[start] = 1;
		q.push(head);
		while (!q.empty() && q.front().num != end) {
			digit(q.front());
			q.pop();
		}
		if (q.empty()) {
			cout << "Impossible" << endl; 
		} else {
			cout << q.front().cnt << endl;			
		}
	}
	return 0;
}