#include<iostream>
#include<map>
#include<queue>
#include<stack>
using namespace std;

queue<int>Q;
map<int, int>vis;     //记录该状态是否被访问过
map<int, int>step;      //记录层数
map<int,int>parent;     //记录该状态的上一个状态
stack<int>out;
int dis[4][2] = { -1,0,0,1,1,0,0,-1 };     //左、上、右、下
int u, v;

int change(int** p, int a, int b)   //把数组矩阵转为一串数字
{
    int t = 0;
    for (int i = 0; i < a; i++)
        for (int j = 0; j < b; j++)
            t = t * 10 + p[i][j];
    return t;
}

int bfs(int** p, int a, int b)    //广度搜索
{
    int x, y, uu;    //x,y--空格所在的行列号，uu--队头八字码状态
    Q.push(u);     //把初始状态放入队列
    vis[u] = 1;      //被访问过标记为1
    step[u] = 0;      //初始层数为0
    while (Q.size())       //队空搜索结束
    {
        uu = u = Q.front();
        Q.pop();
        if (u == v)
            return step[v];
        for(int i=a-1;i>=0;i--)       //把八字码状态的数字转为数组
            for (int j = b - 1; j >= 0; j--)
            {
                p[i][j] = uu % 10, uu = uu / 10;
                if (p[i][j] == 0)     //标记空格位置
                    x = i, y = j;
            }
        for (int i = 0; i < 4; i++)     //空格四周搜索
        {
            int nu;
            if (!(x == 0 && i == 0) && !(y == b - 1 && i == 1) && !(x == a - 1 && i == 2) && !(y == 0 && i == 3))   //当空格所走位置合理
            {
                p[x][y] = p[x + dis[i][0]][y + dis[i][1]], p[x + dis[i][0]][y + dis[i][1]] = 0;     //交换空格位置
                nu = change(p, a, b);
                if (!vis[nu])      //若该状态没有被访问过
                {
                    Q.push(nu);      //入队
                    vis[nu] = 1;
                    step[nu] = step[u] + 1;     //层数在上一个状态层数上加一
                    parent[nu] = u;          //记录该状态的父状态
                }
                p[x + dis[i][0]][y + dis[i][1]] = p[x][y], p[x][y] = 0;      //还原空格位置继续搜索
            }
        }
    }
    return -1;
}

int main()
{
    cout << "广度搜索" << endl;
    int m, n, s, t;
    int** mau, ** mav;
    cout << "输入m*n；" << endl;
    cin >> m >> n;
    mau = new int* [n], mav = new int* [n];
    for (int i = 0; i < n; i++)
        mau[i] = new int[m], mav[i] = new int[m];
    cout << "初始状态:" << endl;
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            cin >> mau[i][j];
    cout << "最终状态:" << endl;
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            cin >> mav[i][j];
    u = change(mau, m, n), v = change(mav, m, n);
    s = bfs(mau, m, n);
    if (s != -1)       //返回层数
    {
        cout << "到达目标状态需要 " << s << " 步" << endl;
        t = v;
        while (t)        //把所有的父状态入栈
        {
            out.push(t);
            t = parent[t];
        }
        while (out.size())      //输出目标状态的八字码求解过程
        {
            int** o;
            t = out.top();
            out.pop();
            o = new int* [n];
            for (int i = 0; i < n; i++)
                o[i] = new int[m];
            for (int i = m - 1; i >= 0; i--)
                for (int j = n - 1; j >= 0; j--)
                    o[i][j] = t % 10, t /= 10;
            for (int i = 0; i < m; i++)
            {
                for (int j = 0; j < n; j++)
                    cout << o[i][j] << " ";
                cout << endl;
            }
            cout << "======" << endl;
        }
    }
    else cout << "无解" << endl;     //没有返回层数
}