本文共 1587 字，大约阅读时间需要 5 分钟。

问题描述

　　如下面第一个图的九宫格中，放着 1~8 的数字卡片，还有一个格子空着。与空格子相邻的格子中的卡片可以移动到空格中。经过若干次移动，可以形成第二个图所示的局面。

　　我们把第一个图的局面记为：12345678. 　　把第二个图的局面记为：123.46758 　　显然是按从上到下，从左到右的顺序记录数字，空格记为句点。 　　本题目的任务是已知九宫的初态和终态，求最少经过多少步的移动可以到达。如果无论多少步都无法到达，则输出-1。

输入格式

　　输入第一行包含九宫的初态，第二行包含九宫的终态。

输出格式

　　输出最少的步数，如果不存在方案，则输出-1。

样例输入

12345678.

123.46758

样例输出

3

样例输入

13524678.

46758123.

样例输出

22

思路：

bfs，通过康拓展开来标记出现的状态。

代码如下：

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;const int maxn=362885;char s[15];char e[15];int vis[maxn];int fin;int a[15];int b[15];int fn[10];int pos[4][2]={
  {1,0},{-1,0},{0,1},{0,-1}};int px,py;struct node{    int a[15];    int px,py;    int step;};int can (int x[]){    int ans=0;    for (int i=0;i<9;i++)    {        int num=0;        for (int j=i+1;j<9;j++)        {            if(x[i]>x[j]) num++;        }        ans+=fn[9-i-1]*num;    }    return ans;}int bfs (){    node now,next;    queue
        
         q; memcpy(now.a,a,sizeof(now.a)); now.px=px; now.py=py; vis[can(now.a)]=1; now.step=0; q.push(now); while(!q.empty()) { now=q.front(); q.pop(); int t=can(now.a); if(t==fin) return now.step; for (int i=0;i<4;i++) { next=now; next.step++; int tx=now.px+pos[i][0]; int ty=now.py+pos[i][1]; if(tx<0||tx>=3||ty<0||ty>=3) continue; swap(next.a[tx*3+ty],next.a[next.px*3+next.py]); int t=can(next.a); if(!vis[t]) { next.px=tx; next.py=ty; vis[t]=1; q.push(next); } } } return -1;}int main(){ fn[0]=1; for (int i=1;i<=9;i++) fn[i]=fn[i-1]*i; memset (vis,0,sizeof(vis)); scanf("%s",s); scanf("%s",e); int len=strlen(s); for (int i=0;i
        
       
      
     
    
   

 

转载地址：http://azoen.baihongyu.com/