pku 3126 bfs

柔情只为你懂 2022-08-13 12:38 9阅读 0赞

\#include <iostream> using namespace std; int n1, n2; bool map\[10000\]; int value\[10000\]; int q\[11000\]; int c\[4\]= \{1, 10, 100, 1000\}; bool bfs() \{ int front = 0, rear = 0; q\[rear++\] = n1; value\[n1\] = 0; while(front < rear) \{ int temp = q\[front++\]; if(temp == n2) return true; for(int i = 0; i < 4; ++i) \{ int digit = (temp/c\[i\]) % 10; for(int j = 0; j < 10; ++j) \{ int changed = temp - digit\*c\[i\] + j\*c\[i\]; //注意判断: changed >= 1000 if(changed >= 1000 && j != digit && map\[changed\] && value\[changed\] == -1) \{ q\[rear++\] = changed; value\[changed\] = value\[temp\]+1; \} \} \} \} return false; \} int main() \{ int n; for(int i = 1; i <= 9999; ++i) map\[i\] = true; for(int i = 2; i < 5000; ++i) if(map\[i\]) \{ for(int j = 2\*i; j <= 9999; j += i) map\[j\] = false; \} scanf("%d", &n); while(n--) \{ scanf("%d%d", &n1, &n2); memset(value, -1, sizeof(value)); if(map\[n1\] && map\[n2\]) \{ if(bfs()) printf("%d/n", value\[n2\]); else printf("Impossible/n"); \} else printf("Impossible/n"); \} return 0; \} //bfs的运用,深搜,一次搞定 //注意判断: changed >= 1000

发表评论取消回复

表情：

评论列表（有 0 条评论，9人围观）

还没有评论，来说两句吧...

相关阅读

相关 POJ 3126 Prime Path(BFS + 素数判定)

题意：给定两个四位素数作为终点和起点，每次可以改变起点数的某一位，且改变后的数仍然是素数，如果变换成终点数字输出最短步数，否则输出Impossible。 includ

雨点打透心脏的1/2处/ 2024年02月17日 19:07/ 0 赞/ 52 阅读

相关 pku 3635 Full Tank? 优先队列+BFS

用二维数组state\[C\]\[fuel\], 表示在城市C油量为fuel时的最小代价. 怎样在一个节点上进行状态转移? 1. 把该节点的油量加1, 以供继续拓展.

野性酷女/ 2022年08月21日 00:21/ 0 赞/ 140 阅读

相关 pku 1915 Knight Moves 双向BFS

最简单的双向BFS, 就不做注释和说明了-\_- \include <stdio.h> \include <iostream> \include <string.h> \in

拼搏现实的明天。/ 2022年08月18日 10:55/ 0 赞/ 104 阅读

相关 pku 3126 bfs

\include <iostream> using namespace std; int n1, n2; bool map\[10000\]; int value\[10000

柔情只为你懂/ 2022年08月13日 12:38/ 0 赞/ 10 阅读

相关 pku 1426 bfs

\include <iostream> using namespace std; \_\_int64 q\[1100000\]; int n; \_\_int64 bfs()

左手的ㄟ右手/ 2022年08月13日 12:38/ 0 赞/ 10 阅读

相关 pku 1101 bfs

/\ //很很很经典的bfs, 这也是我第一次正式用bfs来刷题, 感受颇深: //one.cpp是用bfs来解决从一个点到另一个点的最短路程长度的方法(写的有点冗杂) 注意的

向右看齐/ 2022年08月13日 12:37/ 0 赞/ 161 阅读

相关 pku 1077 Eight 经典8数码问题单向BFS + A* BFS + 双向BFS

本题的判重的状态的保存用到了全排列的变进制hash方法. 详细的解释见: [http://www.cppblog.com/longzxr/archive/2009/08/0

蔚落/ 2022年08月10日 09:35/ 0 赞/ 143 阅读

相关 pku 3414 Pots 经典BFS

1. 基本的状态转移是很好找的. 2. 难点是判重和状态的保存. 判重我用的是visited\[x\]\[y\]二维数组, A为容量x, B为容量y时标记已访问;当再次A为

迈不过友情╰/ 2022年08月10日 00:44/ 0 赞/ 130 阅读

相关 Prime Path POJ - 3126 (BFS,素数距离)

The ministers of the cabinet were quite upset by the message from the Chief of Security

拼搏现实的明天。/ 2022年04月24日 02:58/ 0 赞/ 176 阅读

相关 poj 3126 BFS

BFS得到的一定是最短路径。开始我还在纠结怎么才是最短的呢。其实BFS的题目有个共性（这不废话，哪一类题没有共性啊。呵呵）。以后做这种题自己慢慢总结吧。

柔情只为你懂/ 2021年12月17日 02:57/ 0 赞/ 361 阅读