字串变换

BFS

#include<iostream>
#include<string>
#include<queue>
#include<map>
using namespace std;
map<string, int> maps;
struct node {
  string str; int step;
};
queue<node> q;
string s, x, a[15], b[15];
int n = 0;

string trans(const string &str, int i, int num) {       //待转换字符串，下标，规则
  if (i + a[num].length() > str.length()) return " ";   //字符遍历到头
  for (int j = 0; j < a[num].length(); j++)             //待转换字符串与规则比较
    if (str[i + j] != a[num][j]) return " ";
  string nxt = str.substr(0, i);                        //转换前前部分
  nxt += b[num];                                        //加上转换后部分
  nxt += str.substr(i + a[num].length());               //转换前后部分
  return nxt;
}
void bfs() {
  int ans = 0;                                          //转换步数
  node u, v; u.str = s, u.step = 0;                     //待转换字符
  q.push(u);
  while (!q.empty()) {
    u = q.front(); q.pop();
    if (maps.count(u.str)) continue;                    //去重
    if (u.step > 10) continue;                          //超过十步舍弃
    if (u.str == x) {                                   //转换成功
      ans = u.step; break; 
    }
    maps[u.str] = 1;                                    //标记
    for (int i = 0; i < u.str.length(); i++) {          //字符
      for (int j = 0; j < n; j++) {                     //规则
        v.str = trans(u.str, i, j); 
        if (v.str != " ") {                             //转换成功
          v.step = u.step + 1; q.push(v);               //入队
        }
      }
    }
  }
  if (ans == 0 || ans > 10) cout << "NO ANSWER!"; 
  else cout << ans;
}

int main() {
  cin >> s >> x;                                       //起始字符、结束字符
  while(cin >> a[n] >> b[n]) 
    if (n >= 6)  break;                                 
    n++;                                               //输入规则，记录规则数量
  bfs();
  return 0;
}

笔记：字符串的转换用的for循环嵌套，字符串里有规则的地方都尝试转换，用拼接字符串拿掉旧字符换上新字符，把十步以上的优化掉