#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#include <iomanip>
#include <fstream>

using namespace std;

//moves will be outputted to this filestream
ofstream ofs("PuzzleSolution.txt");

//Puzzle solver
class EPSolver
{
    using ID = uint64_t;
    using P = pair<double, ID>;

public:
    int h, w;

    //Puzzle board
    class Puzzle
    {
    public:
        int h, w;
        EPSolver::ID id;
        vector<vector<int>> board;

        Puzzle(int N = 3, int M = 3)
        {
            h = N, w = M;
            id = 0;
            board.resize(h, vector<int>(w));
            for (int i = 0; i < h; i++)
            {
                for (int j = 0; j < w; j++)
                {
                    board[i][j] = (i == h - 1 && j == w - 1 ? 0 : i * w + j + 1);
                    id = id * h * w + board[i][j];
                }
            }
        }

        Puzzle(const vector<vector<int>> &newboard)
        {
            setBoard(newboard);
        }

        void setBoard(const vector<vector<int>> &newboard)
        {
            h = newboard.size();
            w = newboard[0].size();
            board = newboard;
            id = 0;
            for (int i = 0; i < h; i++)
            {
                for (int j = 0; j < w; j++)
                {
                    board[i][j] = newboard[i][j];
                    id = id * h * w + board[i][j];
                }
            }
            if (!checkInput())
            {
                //cerr << "Invalid Input" << endl;
                exit(0);
            }
        }

        bool checkInput()
        {
            bool res = true;
            set<int> s;
            for (int i = 0; i < h; i++)
            {
                for (int j = 0; j < w; j++)
                {
                    int v = board[i][j];
                    res &= 0 <= v && v < h * w;
                    res &= s.find(v) == s.end();
                    s.insert(v);
                }
            }
            res &= s.size() == (h * w);
            return res;
        }

        //evaluation function
        //a=1安定
        double calcScore(double a = 1.)
        {
            double res = 0;
            for (int i = 0; i < h; i++)
            {
                for (int j = 0; j < w; j++)
                {
                    int k = board[i][j];
                    if (k == 0)
                        continue;
                    int y = (k - 1) / w, x = (k - 1) % w;
                    res += pow(pow(abs(y - i), a) + pow(abs(x - j), a), 1 / a);
                }
            }
            return res;
        }

        double calcScore(int a = 1)
        {
            double res = 0;
            for (int i = 0; i < h; i++)
            {
                for (int j = 0; j < w; j++)
                {
                    int k = board[i][j];
                    if (k == 0)
                        continue;
                    int y = (k - 1) / w, x = (k - 1) % w;
                    res += abs(y - i) + abs(x - j);
                }
            }
            return res;
        }

        friend ostream &operator<<(ostream &os, const Puzzle &puzzle)
        {
            for (int i = 0; i < puzzle.h; i++)
            {
                for (int j = 0; j < puzzle.w; j++)
                {
                    int x = puzzle.board[i][j];
                    os << (char)(x ? x + '0' : '#') << ' ';
                }
                os << '\n';
            }
            return os;
        }
    };

    //ID -> Puzzle
    Puzzle encodeBoard(ID id)
    {
        vector<vector<int>> b(h);
        for (int i = 0; i < h; i++)
        {
            for (int j = 0; j < w; j++)
            {
                b[i].push_back(id % ID(h * w));
                id /= ID(h * w);
            }
            reverse(b[i].begin(), b[i].end());
        }
        reverse(b.begin(), b.end());
        Puzzle p(b);
        return p;
    }

    //score and boardID
    priority_queue<P, vector<P>, greater<P>> open, close;
    set<ID> openId, closeId;

    //child, parent
    map<ID, ID> par;
    map<ID, double> scoreMemoF;
    map<ID, double> scoreMemoG;

    //first state, target state
    ID initId, targetId;

    EPSolver(const vector<vector<int>> &b, const vector<vector<int>> &t)
    {
        h = b.size();
        w = b[0].size();
        Puzzle pb(b), pt(t);
        double s = pb.calcScore(1);
        initId = pb.id;
        targetId = pt.id;
        openId.insert(initId);
        open.push(make_pair(s, initId));
        par[initId] = -1;
        scoreMemoF[initId] = s;
        solve();
    }

    vector<Puzzle> nextBoard(const Puzzle &puzzle)
    {
        vector<Puzzle> res;
        for (int i = 0; i < h; i++)
            for (int j = 0; j < w; j++)
            {
                //find empty cell
                if (puzzle.board[i][j])
                    continue;
                for (int d = 0; d < 4; d++)
                {
                    int ny = i + ((d & 1) ? 0 : ((d & 2) ? 1 : -1));
                    int nx = j + ((d & 1) ? ((d & 2) ? 1 : -1) : 0);
                    if (0 > ny || ny >= h || 0 > nx || nx >= w)
                        continue;
                    vector<vector<int>> copyBoard(puzzle.board);
                    swap(copyBoard[ny][nx], copyBoard[i][j]);
                    Puzzle newpuzzle = Puzzle(copyBoard);
                    res.push_back(newpuzzle);
                }
            }
        return res;
    }

    void solve()
    {
        if (initId == targetId)
        {
            //cerr << "Already Solved (*-v・)" << endl;
            return;
        }
        while (!open.empty())
        {
            //openから一番いいものを採用
            double score = open.top().first;
            ID id = open.top().second;

            open.pop();
            //openから削除、closeに追加
            openId.erase(openId.find(id));
            closeId.insert(id);

            auto newBoard = encodeBoard(id);
            auto nextState = nextBoard(newBoard);

            for (auto board : nextState)
            {
                ID nextId = board.id;
                if (!scoreMemoG[nextId] || scoreMemoG[nextId] < scoreMemoG[id] + 1)
                {
                    scoreMemoG[nextId] = scoreMemoG[id] + 1;
                }
                double score = board.calcScore(1) + scoreMemoG[nextId];
                if (nextId == targetId)
                {
                    //cerr << "Solution Was Found!" << endl;
                    par[nextId] = id;
                    return;
                }
                bool foundInOpen = openId.find(nextId) != openId.end();
                bool foundInClose = closeId.find(nextId) != closeId.end();
                if (not foundInOpen and not foundInClose)
                {
                    open.push({score, nextId});
                    openId.insert(nextId);
                    scoreMemoF[nextId] = score;
                    par[nextId] = id;
                }
                else if (foundInClose)
                {
                    if (score < scoreMemoF[nextId])
                    {
                        scoreMemoF[nextId] = score;
                        par[nextId] = id;
                        openId.insert(nextId);
                        open.push({score, nextId});
                    }
                }
                else if (foundInOpen)
                {
                    if (score < scoreMemoF[nextId])
                    {
                        scoreMemoF[nextId] = score;
                        par[nextId] = id;
                    }
                }
            }
        }
        //cerr << "Solution Was Not Found..." << endl;
        return;
    }

    void traceBack()
    {
        ID p = targetId;
        vector<ID> path;
        while (p != -1)
        {
            //ofs << p << ' ' << par[p] << endl;
            path.push_back(p);
            p = par[p];
        }
        cout << path.size() - 1 << endl;
        //cerr << "Number of moves: " << path.size() - 1 << endl;
        reverse(path.begin(), path.end());
        int cnt = 0;
        for (auto i : path)
        {
            ofs << "move " << cnt++ << '\n'
                << encodeBoard(i) << endl;
        }
    }
};

int main()
{
    int n = 3;
    // vector<vector<int>> easy = {{5, 3, 4}, {1, 2, 6}, {7, 8, 0}};
    // vector<vector<int>> hard = {{0, 6, 3}, {5, 8, 2}, {7, 4, 1}};
    vector<vector<int>> b(n, vector<int>(n)), t(b);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
        {
            cin >> b[i][j];
            t[i][j] = i * n + j + 1;
        }
    t.back().back() = 0;
    EPSolver eps(b, t);
    eps.traceBack();
    return 0;
}


Measured memory_bytes: 5284