描写叙述

如以下第一个图的九宫格中，放着 1~8 的数字卡片，另一个格子空着。与空格子相邻的格子中的卡片能够移动到空格中。经过若干次移动。能够形成第二个图所看到的的局面。　　我们把第一个图的局面记为：12345678.　　把第二个图的局面记为：123.46758　　显然是按从上到下。从左到右的顺序记录数字，空格记为句点。　　本题目的任务是已知九宫的初态和终态，求最少经过多少步的移动能够到达。假设不管多少步都无法到达，则输出-1。

 

输入

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

输出

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

例子输入

12345678.

123.46758

例子输出

3

#include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;char str1[20];///终态int jc[10] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};///1到10的阶乘int dir[] = {0, 1, 0, -1, 0};///方向bool f[1000000];struct node {    char str[10];//当然状态    int step;//步数    int loc;//空格位置};int fun(char str[])//状态匹配{    for (int i = 0; i < 9; i++) {        if (str[i] != str1[i])return false;    }    return true;}int por(string a)//康托展开{    int size = 0;    for (int i = 0; i < 9; i++) {        int len = 0;        for (int j = i + 1; j < 9; j++) {            if (a[i] > a[j])len++;        }        size += len * jc[8 - i];    }    return size;}int bfs(node x){    queue
          
           q;    q.push(x);    while (!q.empty()) {        node a = q.front();q.pop();        for (int i = 0; i < 4; i++) {//四个方向         //   cout<
           
            <
            
             = 3 || ay < 0 || ay >= 3)continue; b.str[b.loc] = b.str[ax * 3 + ay];//位置交换 b.str[ax * 3 + ay] = '9'; b.loc = ax * 3 + ay; b.step ++; int index = por(b.str); if (!f[index]) { if (fun(b.str)) { return b.step; } f[index] = true; q.push(b); } } } return -1;}int main(){ node a; while (cin >> a.str >> str1) { memset(f, 0, sizeof(f)); for (int i = 0; i < 9; i++) { if (a.str[i] == '.') {a.str[i] = 9; a.loc = i; a.step = 0;} if(str1[i]=='.')str1[i]='9'; } cout << bfs(a) << endl; } return 0;}