题目链接:http://acm.nyist.net/JudgeOnline/problem.php?pid=592
解决以下问题后就方便用广搜解:
1、将数字坐标化,10000坐标为(0,0),这样就可以通过数字获得其坐标
2、通过一个坐标知道在这个位置上的数字是否为素数
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<queue> using namespace std; #define N 10000 ][]; ][]; bool tprime[N]; ][] = {,, ,, -,, ,-}; struct Point { int x, y; bool isPrime; }c[N+]; struct Node { int x, y, step; bool operator == (const Node &pra) const { return x == pra.x && y == pra.y; } }; void init() { int n = N; , end = (int)sqrt(N+0.5), i; ) { for(i=start; i<=end; i++){ c[n].x = start; c[n--].y = i; } ; i<end; i++){ c[n].x = i; c[n--].y = end; } for(i=end; i>=start; i--){ c[n].x = end; c[n--].y = i; } ; i>start; i--){ c[n].x = i; c[n--].y = start; } start++; end--; } } void initPrime() { memset(tprime, true, sizeof(tprime)); memset(prime, true, sizeof(prime)); prime[c[].x][c[].y] = false; int m = sqrt(N+0.5); ; i<=m; i++){ if(tprime[i]){ for(int j=i*i; j<=N; j+=i){ tprime[j] = false; prime[c[j].x][c[j].y] = false; } } } } int bfs(int a, int b) { memset(vis, false, sizeof(vis)); Node start, target; start.x = c[a].x; start.y = c[a].y; start.step = ; target.x = c[b].x; target.y = c[b].y; queue<Node>que; que.push(start); vis[start.x][start.y] = true; while (!que.empty()) { Node cur = que.front(); que.pop(); if(cur == target) return cur.step; ; i<; i++){ ]; ]; || ty< || tx>N || ty>N || prime[tx][ty] || vis[tx][ty]) continue; vis[tx][ty] = true; Node next; next.x = tx; next.y = ty; next.step = cur.step+; que.push(next); } } ; } int main() { init(); initPrime(); ; while(cin>>a>>b){ int res = bfs(a, b); cout<<"Case "<<(++cnt)<<": "; ){ cout<<res<<endl; } else { cout<<"impossible"<<endl; } } ; }