哦突然想起来这个搜索叫启发式搜索......
#include "bits/stdc++.h" using namespace std; char s[10][10]; int dx[8]={-2,-2,-1,-1,1,1,2,2}; int dy[8]={-1,1,-2,2,-2,2,-1,1}; int ans; char ss[6][6]={"11111","01111","00*11","00001","00000"}; bool ck(){ int i,j; for (i=0;i<5;i++) for (j=0;j<5;j++) if (s[i][j]!=ss[i][j]) return false; return true; } void dfs(int dp,int nx,int ny){ int i,j,zt=0; // for (i=0;i<5;i++){ // printf("%s\n",s[i]); // // }printf("\n\n"); if (dp>15) return; if (ck()){ ans=min(ans,dp); return; } for (i=0;i<5;i++) for (j=0;j<5;j++) if (s[i][j]!=ss[i][j]){ zt++; if (dp+zt>ans) return; } for (i=0;i<8;i++){ if(nx+dx[i]<0 || nx+dx[i]>4 || ny+dy[i]<0 || ny+dy[i]>4) continue; swap(s[nx][ny],s[nx+dx[i]][ny+dy[i]]); dfs(dp+1,nx+dx[i],ny+dy[i]); swap(s[nx][ny],s[nx+dx[i]][ny+dy[i]]); } } int main(){ int i,j,t,nx,ny; scanf("%d",&t); while (t--){ for (i=0;i<5;i++) scanf("\n%s",s[i]); for (i=0;i<5;i++) for (j=0;j<5;j++) if (s[i][j]=='*') nx=i,ny=j; ans=16; dfs(0,nx,ny); printf("%d\n",(ans==16?-1:ans)); } return 0; }