【双向BFS】字串变换题解

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

string A,B;  // 起始字符串A和目标字符串B

// 定义规则结构体，存储字符串变换规则
struct rule{
    string from,to;  // from: 被替换的子串, to: 替换成的子串
};

vector<rule> r;  // 存储所有变换规则的向量

/**
 * 根据当前字符串和方向生成所有可能的下一状态
 * @param cur 当前字符串
 * @param b 方向标志：true表示正向(A->B)，false表示反向(B->A)
 * @return 所有可能变换后的字符串集合
 */
vector<string> build(string cur,bool b){
    vector<string> res;
    // 遍历所有规则
    for(int i=0;i<r.size();i++){
        // 根据方向确定替换的源字符串和目标字符串
        string from=b?r[i].from:r[i].to;  // 正向用from->to，反向用to->from
        string to=b?r[i].to:r[i].from;
        
        size_t pos=0;
        // 在当前字符串中查找所有匹配的from子串
        while((pos=cur.find(from,pos))!=string::npos){
            string nxt=cur;  // 复制当前字符串
            nxt.replace(pos,from.size(),to);  // 替换匹配的子串
            res.push_back(nxt);  // 将新字符串加入结果集
            pos++;  // 移动到下一个位置继续查找
        }
    }
    return res;
}

/**
 * 双向BFS搜索最短变换步数
 * @return 最短步数，如果无法在10步内变换成功返回-1
 */
int bfs(){
    // 如果起始字符串和目标字符串相同，直接返回0步
    if(A==B)
        return 0;
    
    // da: 从A出发到各状态的步数，db: 从B出发到各状态的步数
    map<string,int> da,db;
    // qa: 正向搜索队列，qb: 反向搜索队列
    queue<string> qa,qb;
    
    // 初始化双向搜索
    qa.push(A); da[A]=0;  // A端从起始字符串开始，步数为0
    qb.push(B); db[B]=0;  // B端从目标字符串开始，步数为0
    
    // 双向BFS主循环
    while(!qa.empty()&&!qb.empty()){
        // 选择节点数较少的一端进行扩展，保持搜索平衡
        if(qa.size()<=qb.size()){
            int suma=qa.size();  // 当前层的节点数
            for(int i=0;i<suma;i++){
                string f=qa.front();  // 取出队首节点
                qa.pop();
                
                // 步数限制：单方向最多扩展10步
                if(da[f]>=10)
                    continue;
                
                // 生成所有可能的下一状态（正向扩展）
                vector<string> nxt=build(f,1);
                for(int j=0;j<nxt.size();j++){
                    // 如果新状态在A端已访问过，跳过
                    if(da.count(nxt[j]))
                        continue;
                    // 如果新状态在B端已访问过，找到最短路径
                    if(db.count(nxt[j]))
                        return da[f]+1+db[nxt[j]];  // 总步数 = A端步数 + B端步数 + 当前变换
                    
                    // 记录新状态的步数并加入队列
                    da[nxt[j]]=da[f]+1;
                    qa.push(nxt[j]);
                }
            }
        }
        else{
            // B端扩展，逻辑与A端对称
            int sumb=qb.size();
            for(int i=0;i<sumb;i++){
                string f=qb.front();
                qb.pop();
                
                if(db[f]>=10)
                    continue;
                
                // 反向扩展：使用相反的变换规则
                vector<string> nxt=build(f,0);
                for(int j=0;j<nxt.size();j++){
                    if(db.count(nxt[j]))
                        continue;
                    if(da.count(nxt[j]))
                        return db[f]+1+da[nxt[j]];
                    
                    db[nxt[j]]=db[f]+1;
                    qb.push(nxt[j]);
                }
            }
        }
    }
    return -1;  // 无法在步数限制内找到变换路径
}

int main(){
    // 读取起始字符串和目标字符串
    cin>>A>>B;
    string s1,s2;
    // 读取所有变换规则
    while(cin>>s1>>s2)
        r.push_back({s1,s2});
    
    // 执行双向BFS搜索
    int res=bfs();
    
    // 输出结果：如果找不到解或步数超过10，输出"NO ANSWER!"
    if(res==-1||res>10)  // 注意：这里应该是res>10，不是res>=10
        cout<<"NO ANSWER!";
    else
        cout<<res;
    return 0;
}