题意:给定两个四位数,一个代表密码的初始状态,一个代表密码的开锁状态。对于四位数中的任意一位,可以将其减一或者加一,数字只是1到9,没有0,如果是1,要减一的话,就变成了9,相反,9要加一的话,就变成了1.还可以将两个相邻的位交换,但是最左的位不能和最右的位交换,最右和最左亦然。每改变一次算一步操作。问给定这两种状态,从初始状态到开锁状态最少需要多少步操作?
题解:bfs求解所有状态,最先到达的点的步数肯定最少。
对每一位进行加减和交换处理,特殊情况特殊考虑。
代码:
#include <iostream> #include <queue> #include <cstring> #include <cstdio> using namespace std; const int MAX_ = 10001; bool vis[MAX_]; int d[MAX_]; int last; char str2[10]; int change(char str[]){ int cnt = 0; int len = strlen(str); for(int i = 0; i < len; i++){ cnt = cnt * 10 + str[i] - '0'; } return cnt; } int bfs(char str[]){ queue<int>Q; char s[10]; memset(vis,0,sizeof(vis)); int k = change(str); Q.push(k); vis[k] = 1; d[k] = 0; while(!Q.empty()){ int N = 4,t, tmp = Q.front(); Q.pop(); t = tmp; if(t == last)return d[t]; for(int i = N - 1; i >= 0; i--){ str[i] = '0' + t % 10; t /= 10; } str[N] = '\0'; for(int i = 0; i < N; i++) { if(str[i] > '1') { s[i] = str[i] - 1; } else { s[i] = '9'; } for(int j = 0; j < i; j++) { s[j] = str[j]; } for(int j = i+1; j < N; j++) { s[j] = str[j]; } s[N] = '\0'; t = change(s); if(vis[t])continue; vis[t] = 1; d[t] = d[tmp] + 1; Q.push(t); } for(int i = 0; i < N; i++) { if(str[i] < '9') { s[i] = str[i] + 1; } else { s[i] = '1'; } for(int j = 0; j < i; j++) { s[j] = str[j]; } for(int j = i+1; j < N; j++) { s[j] = str[j]; } s[N] = '\0'; t = change(s); if(vis[t])continue; vis[t] = 1; d[t] = d[tmp] + 1; Q.push(t); } for(int i = 0; i < N; i++){ for(int j = 0; j < N; j++) { s[j] = str[j]; } s[N] = '\0'; if(i == 0){ swap(s[i],s[i+1]); t = change(s); if(vis[t])continue; vis[t] = 1; d[t] = d[tmp] + 1; Q.push(t); continue; } if(i == N - 1){ swap(s[i],s[i-1]); t = change(s); if(vis[t])continue; vis[t] = 1; d[t] = d[tmp] + 1; Q.push(t); continue; } swap(s[i],s[i+1]); t = change(s); if(vis[t])continue; vis[t] = 1; d[t] = d[tmp] + 1; Q.push(t); for(int j = 0; j < N; j++) { s[j] = str[j]; } s[N] = '\0'; swap(s[i],s[i-1]); t = change(s); if(vis[t])continue; vis[t] = 1; d[t] = d[tmp] + 1; Q.push(t); } } return -1; } int main(){ int Case; char str1[10]; scanf("%d",&Case); while(Case--){ scanf("%s%s",str1,str2); last = change(str2); printf("%d\n",bfs(str1)); } return 0; }