这一题需要使用搜索，由于这题数据给的比较小，甚至不用剪枝也能够AC，因为题意也比较直接，所以我们直接来看代码。
#include<iostream> #include<cstdio> using namespace std; const int map_std[6][6] = {{0,0,0,0,0,0}, {0,2,2,2,2,2}, {0,1,2,2,2,2}, {0,1,1,0,2,2}, {0,1,1,1,1,2}, {0,1,1,1,1,1}};//标准图 const int dx[]={-2,-1, 1, 2, 2, 1,-1,-2}; //八个方向 const int dy[]={ 1, 2, 2, 1,-1,-2,-2,-1}; const int maxn = 5 + 5, inf = INT_MAX / 2; int T, ans, exstep, sx, sy; int map_try[maxn][maxn], map_input[maxn][maxn]; bool isend; int get_diffrent() { //获取当前图与标准图有多少棋子不同 int ret = 0; for ( int i = 1; i <= 5; i++ ) for ( int j = 1; j <= 5; j++ ) if ( map_try[i][j] != map_std[i][j] ) ret++; return ret; } bool isgo(int a, int b) { //判断是否越界 if ( a >= 1 && a <= 5 && b >= 1 && b <= 5 ) return true; return false; } void dfs ( int step, int curx, int cury ) { int dif; if ( step > exstep ) return; if ( isend ) return; if ( (dif = get_diffrent()) == 0 ) { //如果达到标准状态 ans = min(ans,step); //更新答案 isend = true; //停止搜索 return; } if ( dif + step - 1 > exstep ) return; //如果无法在期望步数内走完直接停止搜索 for ( int k = 0; k < 8; k++ ) { //枚举出八种走法 int nextx = curx + dx[k]; int nexty = cury + dy[k]; if ( isgo(nextx, nexty) ) { //判断是否越界 swap( map_try[nextx][nexty], map_try[curx][cury] );//尝试这一步走法 dfs (step+1, nextx, nexty);//进行下一步 swap( map_try[nextx][nexty], map_try[curx][cury] );//回溯 } } return; } int main() { char temp[maxn]; cin >> T; while ( T-- ) { isend = false; ans = inf; /**********************\input***********************/ for ( int i = 1; i <= 5; i++ ) { cin >> temp; for ( int j = 1; j <= 5; j++ ) { if ( temp[j-1] != '*' ) map_input[i][j] = temp[j-1] - '0' + 1; else { map_input[i][j] = 0; sx = i; sy = j; } } } /**********************\solve***********************/ for ( exstep = 1; exstep <= 10; exstep++ ) { //期望在十步之内达到标准图状态，所以按exstep=1~10来尝试是否能在exstep内达到标准状态 for ( int i = 1; i <= 5; i++ ) for ( int j = 1; j <= 5; j++ ) map_try[i][j] = map_input[i][j]; dfs(0,sx,sy); if ( ans <= exstep ) break; if ( isend ) break; } if ( ans < inf ) { printf("%d\n", ans); continue; } else printf("-1\n"); } }