原题链接
题意
意思就是，交换K次以内两位数，找出一个最大值和一个最小值
思路
对于最大值和最小值分开来求，分别跑一遍BFS，一个取最大值，一个取最小值。为了方便，可以用字符串的字典序来比大小，效果和数字比大小相同。
然后搜索时，我们用类似冒泡排序的方式进行
- 求max时，当s[i] < s[j]时，再把字符串放进队列
- 求min时，当s[i] > s[j]时，再把字符串放进队列
不然的话，也没有意义。
同时在放入队列时，还要判断第一个字符是不是0，如果是0也不能放入队列。因为题目要求不能有前导0.
最后，再用map标记一下记录步数同时去重。
代码
#include<bits/stdc++.h>
using namespace std;string n;
int k;string bfs_max()
{
string ans = n;queue<string> q;q.push(n);string t = n;unordered_map<string, int> f;f[t] = 0;while (!q.empty()){
t = q.front();q.pop();//至关重要的一步，之前就是因为把这个判断写在了while的括号里导致错了，我** if (f[t] > k) break;ans = max(ans, t);for (int i = 0; i < t.length(); i ++ ){
for (int j = i + 1; j < t.length(); j ++ ){
string neww = t;if (neww[i] < neww[j]){
swap(neww[i], neww[j]);if(!f.count(neww)){
f[neww] = f[t] + 1;if (neww[0] != '0') q.push({
neww});}}}}}return ans ;
}string bfs_min()
{
string ans = n;queue<string> q;q.push(n);string t = n;unordered_map<string, int> f;f[t] = 0;while (!q.empty()){
t = q.front();q.pop();//至关重要的一步，之前就是因为把这个判断写在了while的括号里导致错了，我** if (f[t] > k) break;ans = min(ans, t);for (int i = 0; i < t.length(); i ++ ){
for (int j = i + 1; j < t.length(); j ++ ){
string neww = t;if (neww[i] > neww[j]){
swap(neww[i], neww[j]);if(!f.count(neww)){
f[neww] = f[t] + 1;if (neww[0] != '0') q.push({
neww});}}}}}return ans ;
}
int main()
{
int t;cin >> t;while (t -- ){
cin >> n >> k;cout << bfs_min() <<" " << bfs_max() << endl;}return 0;
}
总结
写了好久，从昨晚一直写到刚刚。。。
看了题解，但还是花了好久。。
原因为把
if (f[t] > k) break;这一步写在了while循环的括号里
错误答案：
殊不知当我取出一个t的步数大于k时，实际上括号中的f[t]还是上一步的，所以就多了一步。。。。
就因为这个，又WA了一会儿。
但凡我聪明一点也不至于会犯这种错误
但凡我自己造个数据测一下也不至于这么久找不出BUG
。。。
然后我自己造了个数据
102 1
102 201
然后就很快发现了问题所在。
康复训练尚未成功，我还需要努力。。。