Author: lllyouo
Date: 20250812
tag: 简单搜索
link: https://www.luogu.com.cn/problem/T574108

问题描述

link

分析

略

参考代码

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

void bfs(string st, string ed) {
    queue<string> q;
    q.push(st);
    map<string, int> dis;
    dis[st] = 1;

    while (q.size()) {
        string s = q.front();
        q.pop();

        // cout << s << " ";

        if (s == ed) break;

        string a = s.substr(s.size() / 2, s.size());
        string b = s.substr(0, s.size() / 2);

        // cout << a << " " << b << " ";
        
        string ns;
        for (int i = 0, j = 0; i < a.size(); i++, j++) {
            ns = ns + a[i] + b[i];
        }

        // cout << ns << endl;
        
        if (dis[ns]) continue;
        
        q.push(ns);
        dis[ns] = dis[s] + 1;
    }

    if (dis[ed]) cout << dis[ed] << endl;
    else cout << -1 << endl;
}

int main() {
    int T; cin >> T;
    for (int id = 1; id <= T; id++) {
        cout << id << " ";
        
        int n; string a, b, ed;
        // 注意输入
        cin >> n >> b >> a >> ed;

        string st;
        for (int i = 0, j = 0; i < a.size(); i++, j++) {
            st = st + a[i] + b[i];
        }

        bfs(st, ed);
    }
    
    return 0;
}