P1132 数字生成游戏 题解

题目

解题思路

暴力bfs，用字符串来模拟这三种操作

用字符串的优点：代码易想，简单易懂，降低思考复杂度，删除/插入操作直接截取字符串再相加就完事了(.substr函数)

缺点：相对直接用数字操作更慢（可能只有我的慢）

交换

最简单的操作，直接交换字符串中的两个字符，然后对应到数字，判断是否要加入队列

删除

枚举删除位置，截取左右两段字符串相加得出新的字符串

插入

枚举插入位置（不能在两头），然后截取左右两段字符串，中间再加一个字符

每次记录答案时需要先将字符串转换为数字 (方法与快读的一样)

注意

x.substr(l, x) 从位置（下标） l 开始取 x 个字符（一开始不知道查了半天样例都没过qwq）

代码

#include <bits/stdc++.h>
using namespace std;
string str, s, v = "0123456789";
int m, st[1000000], inf;
inline int get (string x) {    // get函数将字符串转换为数字 
    int s(0);
    for (int i = 0; i < x.size(); i++)  s = s * 10 + x[i] - 48;
    return s;
}
void Go () {
    queue <pair<string, int> > q;  
    q.push ({str, 0});
    while (q.size()) {
        pair<string, int> t = q.front();  q.pop();
        string stra = t.first;
        int len = stra.size();
        if (len == 1)  continue;    //长度为 1 时不能执行任何操作 
        // 处理交换操作 
        for (int i = 0; i < len; i++)
          for (int j = i + 1; j < len; j++)  {
            string strb(stra);
            swap (strb[i], strb[j]);
            int tmp = get (strb);
            if (st[tmp] > t.second + 1)  
              st[tmp] = t.second + 1, q.push({strb, t.second + 1});
          }
        // 处理删除操作
        for (int i = 0; i < len; i++) {
            string strb = stra.substr (0, i) + stra.substr (i + 1, len - i);
            int tmp = get (strb);
            if (st[tmp] > t.second + 1)  
              st[tmp] = t.second + 1, q.push({strb, t.second + 1}); 
        } 
        // 处理插入操作
        if (len >= str.size())  continue;   // 生成数字不能超出原数字位数
        for (int i = 1; i < len; i++) 
          for (int j = stra[i-1] - 47; j < stra[i] - 48; j++) {
            string strb = stra.substr (0, i) + v[j] + stra.substr (i, len - i);
            int tmp = get (strb);
            if (st[tmp] > t.second + 1)  
              st[tmp] = t.second + 1, q.push({strb, t.second + 1});     
          }
    }
}
int main() {
    cin >> str;
    memset (st, 0x7f, sizeof (st));  inf = st[0];
    st[get(str)] = 0;
    Go ();    
    scanf ("%d", &m);
    while (m--)  
      cin >> s, printf ("%d
", (st[get(s)] == inf) ? -1 : st[get(s)]);
    return 0;
}