代码 提交记录

#include <bits/stdc++.h>
using namespace std;
string nums = "";
int n;
int ans = 5050;
map <string,bool> vis;
map <string,bool> leg;
void init(string s,bool used[]){
    if(s.length()==n*2){
        bool isLeg = 1;
        for(int i=0;i<s.length()-1;i+=2){
            if(s[i]!=s[i+1])    {isLeg = 0;break;}
        }
        leg[s] = isLeg;
    }
    else{
        for(int i=0;i<n*2;i++){
            if(!used[i]){
                used[i] = 1;
                init(s+nums[i],used);
                used[i] = 0;
            }
        }
    }
}
void search(int l,int r,int now,string num){
    string ns = num;
    // cout << l << " " << r << " " << now << " " << (now>ans) << " " << vis[ns] << endl;
    if(now>ans || vis[ns]) return;
    else{
        bool get = leg[ns];
        if(get && now<ans){ans = now;return;}
        else{
            vis[num] = 1;
            char t;
            for(int j=0;j<n*2-1;j++){
                ns = num;
                if(ns[j]!=ns[j+1]){
                    t = ns[j];ns[j] = ns[j+1];ns[j+1] = ns[j];
                    search(j,j+1,now+1,ns);
                }
            }
        }
    }

    
}
// void bfs(int num[]){

// }
int main(){
    scanf("%d\n",&n);
    string tmp;
    getline(cin,tmp);
    for(int i=0;i<tmp.length();i++){
        if(tmp[i]!=' ') nums+=tmp[i];
        // cout << tmp[i];
    }
    bool used[n*2];
    memset(used,0,sizeof(used));
    init("",used);
    for(int j=0;j<n*2-1;j++){
        if(nums[j]!=nums[j+1])  search(j,j+1,0,nums);
    }
    cout << ans;
    return 0;
}