这是做的第一道BFS，很基础很简单的题目
广度优先搜索算法如下：（用QUEUE）
(1) 把初始节点S0放入Open表中；
(2) 如果Open表为空，则问题无解，失败
退出；
(3) 把Open表的第一个节点取出放入
Closed表，并记该节点为n；
(4) 考察节点n是否为目标节点。若是，
则得到问题的解，成功退出；
(5) 若节点n不可扩展，则转第(2)步；
(6) 扩展节点n，将其不在Closed表和
Open表中的子节点(判重）放入Open表的尾部
，并为每一个子节点设置指向父节点的指针(
或记录节点的层次），然后转第(2)步。
一层一层的往深了的搜索，直到遇到所求解。那么深度就是最短步数，还有要注意判重，其中visited数组就起到了判重的作用。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
int n, k;
const int maxn = ;
int visited[maxn + ]; //判重标记
struct Step
{
int x;
int steps;
Step(int xx, int s):x(xx), steps(s){}
};
queue<Step> q;
int main(void)
{
scanf("%d%d", &n, &k);
memset(visited, , sizeof(visited));
q.push(Step(n, ));
visited[n] = ;
while(!q.empty())
{
Step s = q.front();
if(s.x == k)
{//找到目标
printf("%d\n", s.steps);
return ;
}
else
{
if(s.x - >= && !visited[s.x-])
{
q.push(Step(s.x-, s.steps+));
visited[s.x-] = ;
}
if(s.x + <= maxn && !visited[s.x+])
{
q.push(Step(s.x+, s.steps+));
visited[s.x+] = ;
}
if(s.x* <= maxn && !visited[s.x*])
{
q.push(Step(s.x*, s.steps+));
visited[s.x*] = ;
}
q.pop();
}
}
return ;
}
代码君