记一道很综合的bfs

#include<bits/stdc++.h> using namespace std; struct node{ string str; int sum=0; }; map<string,int>ma; string x1[7],x2[7]; int n=1; string initial; string terminal; int tim; int p=0; bool check(string str ,int k){ p=str.find(x1[k]); if(p==-1)return false; else return true; } int main(){ string a; string b; cin>>initial>>terminal; while(cin>>a>>b){ x1[n]=a; x2[n]=b; n++; //if(n==5)break; } n--; int flag=1; struct node node; node.str=initial; queue<struct node> que; que.push(node); //初始点入队 while(!que.empty()){ struct node f=que.front(); que.pop(); if(ma[f.str]==1)continue; ma[f.str]=1; if(f.str==terminal||f.sum>10){ tim=f.sum; flag=0; break;} for(int k=1;k<=n;k++) if(check(f.str,k)){//第一次定位 struct node d=f; d.str.replace(p,x1[k].length(),x2[k]); d.sum++; que.push(d); struct node tem=f; while(1){ //排除第一次后的循环检测 tem.str[p]='`';//tem用来定位 if(check(tem.str,k)){ struct node s=f; s.str.replace(p,x1[k].length(),x2[k]); s.sum++; que.push(s); } if(p==-1)break; } } } if(flag==1)cout<<"NO ANSWER!"; if(tim<=10&&flag==0)cout<<tim; else if(flag==0)cout<<"NO ANSWER!"; system("pause"); return 0; } 很明显，求最短路径必须宽搜，因为深搜你判断最短必须全部搜完必超时。 判断是否可以改变使用string类里面的replace、find、str函数 几个细节很关键： 1. 要使用map容器判断已经入栈的元素剪枝，map实在太好用了，广义数组的感觉，比如map<string,int >就可以 map[string]=1来标记 2. 要被替换的字符串在第i种方式下替换之后还要进行判定后面的字符串能不能再被替换，要用到两个字符串，一个用来修改并且定位，另外一个用来入队