8.19小红书笔试第二题卡9%（bfs做法）

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <queue>
#include <set>
using namespace std;

unordered_map<string,string> map;//合法的变换
unordered_map<string,string> map1;//合法的变换

bool judge(string st){
    string temp;
    for(int i = st.size()-1;i>=0;i--){
        temp.push_back(st[i]);
    }
    if(temp == st){
        return true;
    }
    return false;
}

int search(string start){
    queue<string> que;
    set<string> visited;
    que.push(start);
    visited.insert(start);

    while(!que.empty()){
      int sz = que.size();
      for(int u=0;u<sz;++u){
        string front = que.front();que.pop();
        if(judge(front)){
            return 1;
        }
        for(int i=0;i<front.size();i++){
            string temp;
            temp.push_back(front[i]);
            if(!map.count(temp)&&!map1.count(temp)){
                continue;
            }
            if(map.count(temp) && !map1.count(temp)){
                string forward;
                string back;
                string addst = forward.assign(front.begin(),front.begin()+i) + map[temp] + back.assign(front.begin()+i+1,front.end());
                if(visited.count(addst)==0){
                    que.push(addst);
                    visited.insert(addst);
                }
                continue;
            }
            if(!map.count(temp) && map1.count(temp)){
                string forward;
                string back;
                string addst = forward.assign(front.begin(),front.begin()+i) + map1[temp] + back.assign(front.begin()+i+1,front.end());
                if(visited.count(addst)==0){
                    que.push(addst);
                    visited.insert(addst);
                }
                continue;
            }
            if(map.count(temp) && map1.count(temp)){
                string forward;
                string back;
                string addst = forward.assign(front.begin(),front.begin()+i) + map[temp] + back.assign(front.begin()+i+1,front.end());
                string addst1 = forward.assign(front.begin(),front.begin()+i) + map1[temp] + back.assign(front.begin()+i+1,front.end());
                if(visited.count(addst)==0){
                    que.push(addst);/*添加下一层待访问的节点*/
                    visited.insert(addst);
                }
                if(visited.count(addst1)==0){
                    que.push(addst1);/*添加下一层待访问的节点*/
                    visited.insert(addst1);
                }
            }
        } 
      }
    }
    return 0;
}


int main() {
    int n;
    cin>>n;
    vector<string> vec;
    vector<int> res;
    string temp;
    for(int i=0;i<n;++i){
        cin>>temp;
        vec.push_back(temp);
    }

    map["m"] = "nn";
    map["w"] = "vv";

    map["b"] = "d";
    map["p"] = "q";
    map["d"] = "b";
    map["q"] = "p";

    map1["b"] = "q";
    map1["q"] = "b";
    map1["d"] = "p";
    map1["p"] = "d";

    map["n"] = "u";
    map["u"] = "n";

    for(int i=0;i<vec.size();++i){
        res.push_back(search(vec[i]));
    }

    for(int i=0;i<res.size();++i){
        string ss = res[i]==1 ? "YES" : "NO";
        cout<<ss<<endl;
    }


    return 0;

}

路过的大佬帮忙看看，为啥本地用例都对，提交就是9%啊

用的bfs，自己试了好多都是对的，错的测试用例都是啥呀