#include "stdio.h"
#include <stdlib.h>

typedef struct Node
{
    struct Node *parent;
    struct Node *next;
    int num[9];
}QNode;

int cansolve(int num1[], int num2[]);
void input(int num[]);
int move_up(int num[]);
int move_down(int num[]);
int move_left(int num[]);
int move_right(int num[]);
void get_num(QNode *node, int temp[]);
void set_num(QNode *node, int temp[]);
void print(QNode *node);
int isequal(QNode *node, int temp[]);
int exist(QNode *node, int temp[]);

void main()
{
    int init[9], target[9], temp[9];
    int find = 0;
    QNode *front , *rear, *new_node, *p;
   
   
    printf("输入初始状态:\n");
    input(init);
    printf("输入目标状态:\n");
    input(target);
   
    if (!cansolve(init, target))
    {
        printf("不能实现\n");
        return;
    }
    front = (QNode *)malloc(sizeof(QNode));
    set_num(front, init);
    front->parent = NULL;
    front->next = NULL;
    rear = front;
   
   
    while (front != NULL && !find)
    {
        if (isequal(front, target))
        {
            find = 1;
            break;
        }
        get_num(front, temp);
        if (move_up(temp) && !exist(front, temp))
        {
            new_node = (QNode *)malloc(sizeof(QNode));
            set_num(new_node, temp);
            new_node->parent = front;
            new_node->next = NULL;
            rear->next = new_node;
            rear = new_node;
        }
        
        get_num(front, temp);
        if (move_down(temp) && !exist(front, temp))
        {
            new_node = (QNode *)malloc(sizeof(QNode));
            set_num(new_node, temp);
            new_node->parent = front;
            new_node->next = NULL;
            rear->next = new_node;
            rear = new_node;
        }
        
        get_num(front, temp);
        if (move_left(temp) && !exist(front, temp))
        {
            new_node = (QNode *)malloc(sizeof(QNode));
            set_num(new_node, temp);
            new_node->parent = front;
            new_node->next = NULL;
            rear->next = new_node;
            rear = new_node;
        }
        
        get_num(front, temp);
        if (move_right(temp) && !exist(front, temp))
        {
            new_node = (QNode *)malloc(sizeof(QNode));
            set_num(new_node, temp);
            new_node->parent = front;
            new_node->next = NULL;
            rear->next = new_node;
            rear = new_node;
        }
        
        front = front->next;
    }
   
    if (find)
    {
        for (p = front; p != NULL; p = p->parent)
        {
            printf("--^--\n");
            print(p);
        }
    }
   
   
}

int cansolve(int num1[], int num2[])
{
    int i, j;
    int sum1 = 0, sum2 = 0;
   
    for (i = 0; i < 9; i++)
        for (j = 0; j < i; j++)
        {
            if (num1[j] > num1[i] && num1[i] != 0) ++sum1;
            if (num2[j] > num2[i] && num2[i] != 0) ++sum2;
        }
        
    if (sum1 % 2 == sum2 % 2) return 1;
    else return 0;
}

void input(int num[])
{
    int i, j;
    int flag ;
   
    for (i = 0; i < 9; i++)
    {
        flag = 1;
        scanf("%d", &num[i]);
        if (num[i] < 0 || num[i] > 8) flag = 0;
        
        for (j = 0; j < i && flag; j++)
            if (num[j] == num[i]) flag = 0;
        
        if (flag == 0)
        {
            i--;
            printf("illegal number\n");
        }
    }   
}

int move_up(int num[])
{
    int i;
   
    for (i = 0; i , 9; i++)
        if (num[i] == 0) break;
        
    if (i == 0 || i == 1 || i == 2)
        return 0;
    else
    {
        num[i] = num[i - 3];
        num[i - 3] = 0;
        return 1;
    }
}

int move_down(int num[])
{
    int i;
   
    for (i = 0;  i < 9; i++)
        if (num[i] == 0) break;
        
    if (i == 6 || i == 7 || i == 8)
        return 0;
    else
    {
        num[i] = num[i + 3];
        num[i + 3] = 0;
        return 1;
    }
}

int move_left(int num[])
{
    int i;
   
    for (i = 0; i < 9; i++)
        if (num[i] == 0) break;
        
    if (i == 0 || i == 3 || i == 6)
        return 0;
    else
    {
        num[i] = num[i - 1];
        num[i - 1] = 0;
        return 1;
    }
}

int move_right(int num[])
{
    int i;
   
    for (i = 0; i < 9; i++)
        if (num[i] == 0) break;
   
    if (i == 2 || i == 5 || i == 8)
        return 0;
    else
    {
        num[i] = num[i + 1];
        num[i + 1] = 0;
        return 1;
    }
}

void get_num(QNode *node, int temp[])
{
    int i;
   
    for (i = 0; i < 9; i++)
    {
        temp[i] = node->num[i];
    }
}

void set_num(QNode *node, int temp[])
{
    int i;
   
    for (i = 0; i < 9; i++)
        node->num[i] = temp[i];
}

void print(QNode *node)
{
    int i;
   
    for (i = 0; i < 9; i++)
    {
        printf("%d ", node->num[i]);
        if ((i + 1) % 3 == 0)
            printf("\n");
    }
}

int isequal(QNode *node, int target[])
{
    int i;
    int flag = 1;
   
    for (i = 0; i < 9 && flag; i++)
    {
        if (node->num[i] != target[i])
            flag = 0;
    }
   
    return flag;
}

int exist(QNode *node, int temp[])
{
    QNode *p;
   
    for (p = node; p != NULL; p = p->parent)
        if (isequal(node, temp))
            return 1;
   
    return 0;
}