查了好多资料,发现还是不全,干脆自己整理吧,至少保证在我的做法正确的,以免误导读者,也是给自己做个记录吧!
题意:从一个四位素数变到另一个四位素数,每次只能改到一个位的数字,且修改后仍是一个四位素数,问最少须要几步。
题目链接:http://poj.org/problem?id=3126
——>>直接广搜。
#include <cstdio> #include <cstring> #include <queue> using namespace std; const int maxn = 9999 + 10; int MAP[maxn], a, b, p[maxn], cnt; bool vis[maxn]; int translate(int x, int i, int j) //把x的第i位变成j { int k, buf[4], ret = 0; for(k = 0; k < 4; k++) { buf[k] = x % 10; x /= 10; } buf[i] = j; for(k = 3; k >= 0; k--) ret = ret * 10 + buf[k]; return ret; } bool bs(int* A, int x, int y, int v) //二分搜索 { int m; while(x < y) { m = x + (y - x) / 2; if(A[m] == v) return 1; else if(A[m] > v) y = m; else x = m + 1; } return 0; } void get_prime() //倏地筛素数 { memset(vis, 0, sizeof(vis)); cnt = 0; for(int i = 2; i <= 9999; i++) if(!vis[i]) { p[cnt++] = i; for(int j = i; j <= 9999; j = j + i) vis[j] = 1; } } void bfs() { if(a == b) return; int temp, i, j; queue<int> qu; qu.push(a); while(!qu.empty()) { temp = qu.front(); qu.pop(); for(i = 0; i < 4; i++) for(j = 0; j < 10; j++) { if(j == 0 && (i == 0 || i == 3)) continue; int tmp = translate(temp, i, j); if(tmp % 2 == 0 || MAP[tmp] != -1) continue; if(bs(p, 168, cnt, tmp)) { MAP[tmp] = MAP[temp] + 1; if(tmp == b) return; qu.push(tmp); } } } } int main() { int T; get_prime(); scanf("%d", &T); while(T--) { scanf("%d%d", &a, &b); memset(MAP, -1, sizeof(MAP)); MAP[a] = 0; bfs(); printf("%d\n", MAP[b]); } return 0; }
文章结束给大家分享下程序员的一些笑话语录: 联想——对内高价,补贴对外倾销的伟大“民族”企业。
---------------------------------
原创文章 By
个位和数字
---------------------------------