#广度优先遍历应用#玛雅人的密码#清华大学机试

https://www.acwing.com/problem/content/3388/

思路:本题难点在于,如何确保所有可能的子序列都被遍历到,还要保证不能重复遍历。相比于深度优先,广度优先一层一层来的思想更好的保证了这一基本原则,把每一经过旋转的子序列看作是下一层,同时维护一个数据结构记录是否被访问即可

解法

1.读入数据,若数据小于4直接返回-1;若大于,则维护一个无序map记录是否被访问,一个辅助队列进行广度优先遍历,一个cur字符串记录当前的子序列。将原始字符串压入栈中

2.当栈不为空时,先弹出栈顶字符串检查是否有2012,语法采用cur.find("2012" )!= string::npos,如有则输出对应的distance值并退出执行,如没有则继续

3.从0到cur.size()-1遍历字符串,挨个进行交换:如果在map里面没有找到对应的字符串next,则证明未被访问过。将该节点的键值对插入maps,值设置为cur的distance值+1;

4.循环结束,如果栈为空,直接打印-1

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    char strarr[20] = {0};
    scanf("%d", &n);
    scanf("%s", strarr);
    if (n < 4) {
        printf("-1\n");
        return 0;
    }

    string str = strarr;
    queue<string> toVisit;
    unordered_map<string, int> distance;
    distance.insert({str, 0});
    toVisit.push(str);
    while (!toVisit.empty()) {
        string cur = toVisit.front();
        if (cur.find("2012") != string ::npos) {
            printf("%d\n", distance[cur]);
            break;
        }
        toVisit.pop();

        for (int i = 0; i < cur.size() - 1; i++) {
            string next = cur;//next负责记录两元素翻转之后的下一个字符串
            char tmp = next[i];
            next[i] = next[i + 1];
            next[i + 1] = tmp;//完成交换
            if(distance.count(next) == 0){
                toVisit.push(next);
                distance.insert({next,distance[cur]+1});
            }

        }

    }
    if(toVisit.empty()){
        printf("-1\n");
    }
    return 0;
}

全部评论

相关推荐

点赞 评论 收藏
分享
10-15 03:05
门头沟学院 Java
CADILLAC_:凯文:我的邮箱是死了吗?
点赞 评论 收藏
分享
评论
1
1
分享
牛客网
牛客企业服务