[数据结构与算法]宽度优先算法

Catch That Cow

农夫知道一头牛的位置，想要抓住它。农夫和牛都于数轴上 ，农夫起始位于点 N(0<=N<=100000) ，牛位于点 K(0<=K<=100000) 。农夫有两种移动方式： 1、从 X移动到 X-1或X+1 ，每次移动花费一分钟 2、从 X移动到 2*X ，每次移动花费一分钟 假设牛没有意识到农夫的行动，站在原地不。最少要花多少时间才能抓住牛？
Input
一行: 以空格分隔的两个字母: N 和 K
Output
一行: 农夫抓住牛需要的最少时间，单位分钟
Sample Input
5 17
Sample Output
4

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>

using namespace std;

const int maxn = 100001;

struct Status {
    int n, t;//分别代表所在坐标和当前时间
    Status(int n, int t) : n(n), t(t) {}
};

bool visit[maxn];//记录是否去过某个坐标点，以便下次经过时不再重复记录

int BFS(int n, int k) {
    queue<Status> myQueue;
    myQueue.push(Status(n, 0));//压入初始状态
    visit[n] = true;//起始点已被访问
    while (!myQueue.empty()) {
        Status current = myQueue.front();
        myQueue.pop();
        if (current.n == k) {//说明已经抵达k坐标查找成功
            return current.t;//返回所用时间
        }
        for (int i = 0; i < 3; i++) {//转入不同的状态
            Status next(current.n, current.t + 1) {//直接使用构造函数进行初始化
                if (i == 0) next.n += 1;
                else if (i == 1) next.n -= 1;
                else next.n *= 2;
            }
            if (next.n < 0 || next.n >= maxn || visit[next.n]) {
                continue;//状态不合法，直接继续
            }
            myQueue.push(next);//压入新的状态
            visit[next.n] = true;//标记新压入的状态为已访问
        }
    }
}

int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    memset(visit, false, sizeof(visit));
    printf("%d\n", BFS(n, k));
    return 0;
}

Find The Multiple

给定正整数n，编写程序找出非零值n的倍数m，且m的十进制数表示仅含数字0和1。假设n不大于200，且有不超过100位的相应m。
思考用什么方式降低时间复杂度：由0和1组成的数字num作为一个搜索状态，能由num扩展得到的状态有两个，一个是10num,一个是10num+1。可以通过状态的扩展覆盖整个查找空间中由0和1组成的数

#include<iostream>
#include<cstdio>
#include<queue>

using namespace std;

void BFS(int n) {
    queue<long long> myQueue;
    myQueue.push(1);//压入初始状态
    while (!myQueue.empty()) {
        long long current = myQueue.front();
        myQueue.pop();
        if (current % n == 0) {//查找成功
            printf("%lld\n", current);
            return;//退出
        }
        myQueue.push(current * 10);
        myQueue.push(current * 10 + 1);
    }
}

int main() {
    int n;
    while (scanf("%d", &n) != EOF) {
        if (n == 0) break;
        BFS(n);
    }
    return 0;
}

清华复试上机|玛雅人的密码

描述
玛雅人有一种密码，如果字符串中出现连续的2012四个数字就能解开密码。给一个长度为N的字符串，（2=<N<=13）该字符串中只含有0,1,2三种数字，问这个字符串要移位几次才能解开密码，每次只能移动相邻的两个数字。例如02120经过一次移位，可以得到20120,01220,02210,02102，其中20120符合要求，因此输出为1.如果无论移位多少次都解不开密码，输出-1。
输入描述：
输入包含多组测试数据，每组测试数据由两行组成。 第一行为一个整数N，代表字符串的长度（2<=N<=13）。 第二行为一个仅由0、1、2组成的，长度为N的字符串。
输出描述：
对于每组测试数据，若可以解出密码，输出最少的移位次数；否则输出-1。

#include<iostream>
#include<queue>
#include<string>
#include<unordered_map>//无序容器

using namespace std;

struct NewStr{
    string str;
    int step;//定义经过的步数
    NewStr(int i,string s):step(i),str(s){}//结构体的初始化
};

unordered_map<string, bool> isVisited;//避免重复入队相同的字符串

void bfs(string s){
    queue<NewStr> q;
    q.push(NewStr(0,s));//初始化
    isVisited[s]=true;
    while(!q.empty()){
        NewStr t=q.front();
        q.pop();
        string ts=t.str;//获取当前字符串
        if(ts.find("2012")!=string::npos){
            cout<<t.step<<endl;
            return;
        }
        for(int i=0;i<ts.size()-1;i++){
            swap(ts[i],ts[i+1]);
            if(!isVisited[ts]){//还没有被入队（防止重复访问）
                q.push(NewStr(t.step+1,ts));//步数加一
                isVisited[ts]=true;//设置已被访问
            }
            swap(ts[i],ts[i+1]);//重新交换
        }
    }
    cout<<-1<<endl;//无法解出密码则输出-1
}

int main(){
    int n;
    string s;
    while(cin>>n>>s){
        bfs(s);
    }
    return 0;
}