Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## Re:经典BFS 本人写了半个小时代码 degug一上午 服了 犯了小学生错误 服了

Posted by 201801060731 at 2021-04-08 17:32:41 on Problem 3126
In Reply To:经典BFS 本人写了半个小时代码 degug一上午 服了 犯了小学生错误 服了 Posted by:zhangjiansong at 2020-04-19 11:24:09
```> #include <iostream>
> #include <queue>
> #include <math.h>
>
> using namespace std;
> int isprime(int m)
> {
> 	for(int i = 2; i*i <= m; i++)
> 		if(m % i == 0) return 0;
> 	return 1;
>  }
> void BFS(int n,int k)
> {
> 	int vis[10005] = {0};
> 	int step[10005];
> 	queue <int> q;
> 	q.push(n);
> 	vis[n] = 1;
> 	step[n] = 0;
> 	while(!q.empty()){
> 		q.pop();
> 		for(int i = 0; i < 4; ++i){
> 			for(int j = 0; j <= 9; ++j){ //一开始本人 写成了 i<9 结果又重写了另一个算法 然后发现我这错了 我擦 傻了
> 				if(i == 3 && j == 0) continue;
> 				if(i == 0 ) end = (head/10)*10 + j;
> 				else if(i == 3 ) end = head%1000 + j*1000;
> 				int max = k/1000;
> 				if(!vis[end] && isprime(end)){ //原本想加end1000<max来剪枝的，然后又debug半天发现不能 服了
> 					q.push(end);
> 					vis[end] = 1;
> 					step[end] = step[head] + 1;
> 					if(end == k){
> 						cout << step[end] << endl;
> 						return;
> 					}
> 				}
> 			}
> 		}
> 	}
> 	cout << "Impossible\n"; //我还忘了有impossible 然后又。 服了服了
> }
> int main()
> {
> 	int T;cin >> T;
> 	while(T--){
> 		int n,k;
> 		cin >> n >> k;
> 		if(n == k) cout << 0 << endl;
> 		else BFS(n,k);
> 	}
> }
```

Followed by: