文章

17

粉丝

166

获赞

6

访问

143.7k

头像
字符串bfs
P1162 清华大学上机题
发布于2021年3月5日 19:38
阅读数 9.5k

#include <bits/stdc++.h>
using namespace std;

bool judge(string s)
{
    if(s.find("2012") != string::npos) return true;
    else return false;
}

int bfs(string start)
{
    queue<string> q;
    unordered_map<string, int> d;
    q.push(start);
    d[start] = 0;

    while(q.size())
    {
        auto t = q.front();
        q.pop();

        int distance = d[t];
        if(judge(t)) return distance;

        for(int i = 0; i < t.size() - 1; i++)
        {
            swap(t[i], t[i + 1]);
            if(!d.count(t))
            {
                q.push(t);
                d[t] = distance + 1;
            }
            swap(t[i], t[i + 1]);
        }
    }
    return -1;
}

int main()
{
    int n;
    string start;
    while(cin >> n)
    {
        cin >> start;
        cout << bfs(start) << endl;
    }
    return 0;
}

 

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发