题意：给出(n<=9)长度的两个数字a,b。可以做的操作是在a某一位上加1，或者交换相邻两位的位置。
思路：
直接BFS
如果只有一个节点找去b的话，每个位置的操作为9个加操作和8个交换操作一共17个操作，那么对于9个位置就有17^9次方种
这很明显1s跑不完的！！！
那么我们就要用meet in the middle 的思想 去写
把a,b换成字符串存进队列中。开一个map标记每个字符串的步数与来源（对于a转化来就标记0，对于b转换来就标记1）
那么对于状态0的来说就是加操作，枚举长度然后对每个位做+1操作，要取模10！
那么对于状态1的来说就是减操作，也就是枚举长度然后对每个位做+9操作，也要取模10！ （PS：这个9=-1+10）
那么交换操作无论状态0还是1都是一样的。
那么对于每次我们找到一个状态的s，判断其在hash表（就是那个map）中的来源是否与当前状态来源是否一样，一样则忽略，不一样就可以直接返回去到当前状态的步数+hash表中的状态步数+1
然后特判一开始两个数字相等的情况（如果没有这个就是90分的代码emmm）
#include <bits/stdc++.h> using namespace std; #define ll long long #define re register #define pb push_back #define fi first #define se second const int N=2e6+10; void read(int &a) { a=0;int d=1;char ch; while(ch=getchar(),ch>'9'||ch<'0') if(ch=='-') d=-1; a=ch^48; while(ch=getchar(),ch>='0'&&ch<='9') a=(a<<3)+(a<<1)+(ch^48); a*=d; } int n; string a,b; struct note { string s; int st,f; }; map <string,pair<int,int> > vis; queue <note> q; int bfs() { q.push({a,0,0});q.push({b,0,1}); while(!q.empty()) { note t=q.front(); q.pop(); if(vis.count(t.s)) continue; vis[t.s].fi=t.st;vis[t.s].se=t.f; if(!t.f) { for(re int i=0;i<n;i++) { string s=t.s; s[i]=((s[i]-'0'+1)%10)+'0'; if(vis.count(s)) { if(vis[s].se!=t.f) return vis[s].fi+t.st; else continue; } else q.push({s,t.st+1,t.f}); } for(re int i=1;i<n;i++) { string s=t.s; swap(s[i],s[i-1]); if(vis.count(s)) { if(vis[s].se!=t.f) return vis[s].fi+t.st; else continue; } else q.push({s,t.st+1,t.f}); } } else { for(re int i=0;i<n;i++) { string s=t.s; s[i]=((s[i]-'0'+9)%10)+'0'; if(vis.count(s)) { if(vis[s].se!=t.f) return vis[s].fi+t.st; else continue; } else q.push({s,t.st+1,t.f}); } for(re int i=1;i<n;i++) { string s=t.s; swap(s[i],s[i-1]); if(vis.count(s)) { if(vis[s].se!=t.f) return vis[s].fi+t.st; else continue; } else q.push({s,t.st+1,t.f}); } } } } int main() { for(re int T=1;T<=3;T++) { vis.clear(); while(!q.empty()) q.pop(); read(n); cin>>a>>b; if(a==b) { puts("0"); continue; } printf("%d ",bfs()+1); } return 0; }