本文共 1191 字，大约阅读时间需要 3 分钟。
1 /* 2 BFS简单题：考虑x-1，x+1，x*2三种情况，bfs队列练练手 3 */ 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 using namespace std;13 14 const int MAXN = 1e6 + 10;15 const int INF = 0x3f3f3f3f;16 int n, m;17 int d[MAXN];18 bool vis[MAXN];19 20 void BFS(void)21 {22 memset (vis, 0, sizeof (vis));23 for (int i=0; i<=1e6; ++i) d[MAXN] = 0;24 25 queue q;26 q.push (n); d[n] = 0; vis[n] = true;27 28 while (!q.empty ())29 {30 int x = q.front (); q.pop ();31 if (x == m) break;32 33 int xl = x - 1; int xr = x + 1; int x2 = x * 2;34 35 if (xl >= 0 && !vis[xl])36 {37 q.push (xl); d[xl] = d[x] + 1;38 vis[xl] = true;39 }40 if (xr <= 1e6 && !vis[xr])41 {42 q.push (xr); d[xr] = d[x] + 1;43 vis[xr] = true;44 }45 if (x2 <= 1e6 && !vis[x2])46 {47 q.push (x2); d[x2] = d[x] + 1;48 vis[x2] = true;49 }50 }51 52 }53 54 int main(void) //POJ 3278 Catch That Cow55 {56 //freopen ("POJ_3278.in", "r", stdin);57 58 while (scanf ("%d%d", &n, &m) == 2)59 {60 BFS ();61 printf ("%d\n", d[m]);62 }63 64 return 0;65 }
转载于:https://www.cnblogs.com/Running-Time/p/4444809.html