南阳手机网站推广/新闻发布平台

POJ 3278.Catch That Cow(bfs)(c++)

题目链接：Catch That Cow
题目大意： 给定两个整数n和k。通过 n+1或n-1 或n*2 这3种操作，使得n==k。输出最少的操作次数。
样例：

输入：5 17
输出：4
解释：5-10-9-18-17

解题思路： 可以看成搜索问题，或者bfs典型的迷宫问题，定义一个队列。把起点入队，然后队首出队作为当前位置，把当前位置所能一步到达的位置入队，依次下去，直到，出队的那个当前位置是终点，返回步数。
代码如下：

#include<iostream>
#include<queue>
using namespace std;
int n, k, step = 0;
int vis[100001];            \\vis存储是否已经访问过这个点
#define checkin(x) (x>=0&&x<=100000)      
struct node {           \\checkin判断点是否越界，结构体存储了结点和到达结点需要的最小步数int x, step;
};
int bfs(int dx, int dy) {memset(vis, 0, sizeof(vis));queue<node> q;node start, next;start.x = dx;start.step = 0;q.push(start);vis[dx] = 1;while (!q.empty()) {start = q.front();q.pop();if (start.x == dy) {return start.step;}else {for (int i = 0; i < 3; i++) {if (0 == i) {next.x = start.x + 1;}else if (1 == i) {next.x = start.x - 1;}else {next.x = 2 * start.x;}if (checkin(next.x) && !vis[next.x]) {vis[next.x] = 1;next.step = start.step + 1;q.push(next);}}}}
}
int main()
{cin >> n >> k;cout << bfs(n, k);return 0;
}

补充：这题还可以用vis数组记录结点的步数，这样可以避免结构体。同时在三种方式的选择可以有高明的先后顺序，已达到剪枝的效果。