题意：

给出一个3*3的矩阵，数字0-8，问你能否通过移动组成给定的矩阵，给定矩阵如图所示：
1 2 3
4 5 6
7 8 0

样例：

input：
1 2 3
4 5 6
0 7 8
output：
移动的次数：2
移动的步骤：R->R

题解：

广度优先搜索

代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 3;
const int M = 9;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, -1, 0, 1};
//const char dir[4] = {'U','L','D','R'};
const char dir[][10] = {"U->","L->","D->","R->"};
struct node
{
    int f[M];                  
    int space;                 
    string path;               
    bool operator <(const node &p) const
    {
        for(int i = 0; i < M; i++)
        {
            if(f[i] == p.f[i])
                continue;
            return f[i] > p.f[i];
        }
        return false;
    }
};
bool solve(node p)
{
    for(int i = 0; i < M; i++)
        if(p.f[i] != (i+1))
            return false;

    return true;
}
string bfs(node s)
{
    queue<node> q;
    map<node, bool> V;
    node u, v;
    s.path = "";
    q.push(s);
    V[s] = true;
    while(!q.empty())
    {
        u = q.front();
        q.pop();
        if(solve(u)){
            return u.path;
        }

        int sx = u.space / N;      
        int sy = u.space % N;

        for(int r = 0; r < 4; r++)
        {
            int tx = sx + dx[r];
            int ty = sy + dy[r];
            if(tx < 0 || ty < 0 || tx >= N || ty >= N)
                continue;
            v = u;
            swap(v.f[u.space], v.f[tx*N + ty]);     
            v.space = tx*N + ty;                   
            if(!V[v])                              
            {
                V[v] = true;
                v.path += dir[r];
                q.push(v);
            }
        }
    }
    return "not found";
}
int main()
{
    node a;
    for(int i = 0; i < M; i++){
        cin >> a.f[i];
        if(a.f[i] == 0){
            a.f[i] = M;
            a.space = i;
        }
    }
    string ans = bfs(a);
    if(ans == "not found"){
        cout<<"not found"<<endl;
        return 0;
    }
    cout<<"移动的次数："<<ans.size()/3<< endl;
    cout<<"移动步骤：";
    for(int i=0;i<ans.size()-2;i++)
        cout<<ans[i]; 
}