题意比较好理解
分析一下,从一个数字可以有三种操作,加1,减1,和相邻的换位置,每一个操作,对应一个步骤,问给定一个原始值和目的值,从原始到目的,的最少变换步骤是多少?注意,这里的所有数字只能从1到9
分析:对于每个数,有四位数字,每个数字三种操作,具体说中间的两数字有四种操作,分别和左右换位置,所以从一个数可以走14种状态,也就是14个路到下一个数,注意这里很可能走到重复的数,所以要用一个vis判重,一个数字遍历一遍即可,而且只有这样,才能保证得到是最小值。
那么下面的是代码,对于每个数,枚举它能到12个状态,判一下重即可
代码:
#include <cstdio> #include <queue> #include <cstring> #include <algorithm> using namespace std; const int N = 10010; const int INF = 10000000; int T, sn, en; int num1[5], num2[5], d[N]; bool vis[N]; void towei( int x ) { int i = 3; while ( x > 0 ) { num1[i--] = x%10; x /= 10; } } int tonum( ) { return num2[0] * 1000 + num2[1] * 100 + num2[2] * 10 + num2[3]; } void BFS () { memset( vis, 0, sizeof(vis) ); for ( int i = 0; i < N; ++i ) d[i] = INF; d[sn] = 0; vis[sn] = 1; queue <int> Q; Q.push(sn); while ( !Q.empty() ) { int u = Q.front(); Q.pop(); if ( u == en ) break; towei( u ); int num; for ( int i = 0; i < 4; ++i ) num2[i] = num1[i]; for ( int i = 0; i < 4; ++i ) { //每一位分别加1 if ( num1[i] == 9 ) num2[i] = 1; else num2[i] = num1[i] + 1; num = tonum(); if ( !vis[num] ) { Q.push(num); d[num] = d[u] + 1; vis[num] = 1; } num2[i] = num1[i]; } for ( int i = 0; i < 4; ++i ) { //每一位分别减1 if ( num1[i] == 1 ) num2[i] = 9; else num2[i] = num1[i] - 1; num = tonum(); if ( !vis[num] ) { Q.push(num); d[num] = d[u] + 1; vis[num] = 1; } num2[i] = num1[i]; } for ( int i = 0; i < 3; ++i ) { //与右边相邻的换位置 num2[i+1] = num1[i]; num2[i] = num1[i+1]; num = tonum(); if ( !vis[num] ) { Q.push(num); d[num] = d[u] + 1; vis[num] = 1; } num2[i] = num1[i]; num2[i+1] = num1[i+1]; } for ( int i = 1; i < 4; ++i ) { //与相邻的左边的位置换 num2[i] = num1[i-1]; num2[i-1] = num1[i]; num = tonum(); if ( !vis[num] ) { Q.push(num); d[num] = d[u] + 1; vis[num] = 1; } num2[i] = num1[i]; num2[i-1] = num1[i-1]; } } } int main() { while ( scanf("%d", &T) != EOF ) { while ( T-- ) { scanf("%d%d", &sn, &en); BFS(); printf("%d\n", d[en]); } } }