石子谜题

ccj123

2025-01-23 19:46:44

发布于：上海

16阅读

0回复

0点赞

#include<bits/stdc++.h>
using namespace std;
int n;
string a,b;
struct node{
   int d1,d2;
   string x;
   int d;
};
unordered_map<string,int> mp;
unordered_set<string> set;
int main(){
    cin>>n;
    cin>>a;
    a = a+"..";
    cin>>b;
    b = b+"..";
    queue<node> q;
    q.push({n,n+1,a,0});
    mp[a] = 0;
    while(q.size()){
        node t = q.front();
        q.pop();
        int c1 = t.d1,c2 = t.d2,op = t.d;
        string c = t.x;
        for(int i=0;i<n+1;i++){
            char back1 = c[i],back2 = c[i+1];
            if(c[i]!='.' && c[i+1]!='.'){
                c[c1] = c[i];
                c[c2] = c[i+1];
                c[i] = c[i+1] = '.';
                if(mp.find(c)==mp.end() || mp[c]>op+1){
                    mp[c]=op+1;
                    q.push({i,i+1,c,mp[c]});
                }
            }
            c[c1]=c[c2] = '.';
            c[i] = back1;
            c[i+1] = back2;
        }
    }
    if(mp.find(b)==mp.end())cout<<-1;
    else cout<<mp[b];
    return 0;
}

有帮助，赞一个

去预览

0/2000

这里空空如也

热门讨论