sqsubone_verDuc

#include <bits/stdc++.h>
using namespace std;
const int X[4]={1,-1,0,0};
const int Y[4]={0,0,1,-1};
int n,tr[1000002];
pair <int,int> D[1000002];
struct node{
    int A[12][12];
    bool operator < (const node&a)
    const
    {
        for (int i=1;i<=10;i++)
            for (int j=1;j<=10;j++)
            if (A[i][j]!=a.A[i][j]) return (A[i][j]<a.A[i][j]);
        return false;
    }
};
map <node,int> mp;
node a,b;
struct sosanh{
    bool operator() (const node &s,const node &t)
    const
    {
        int dems=0;int demt=0;
        for (int i=1;i<=10;i++)
            for (int j=1;j<=10;j++)
                if (s.A[i][j]==b.A[i][j]) dems++;
        for (int i=1;i<=10;i++)
            for (int j=1;j<=10;j++)
                if (t.A[i][j]==b.A[i][j]) demt++;
        return (dems<demt);
    }
};

void doc()
{
    int i,j;
    cin>>n;
    for (i=1;i<=n;i++)
        for (j=1;j<=n;j++)
    {
        int x;cin>>x;
        a.A[i][j]=x;
        if (x==0) D[1]={i,j};
    }
    for (i=1;i<=n;i++)
        for (j=1;j<=n;j++)
    {
        int x;
        cin>>x;
        b.A[i][j]=x;
    }
}
void solve()
{
    doc();
    int i,j,l;
    priority_queue <node,vector <node>,sosanh > q;
    int dem=1;
    q.push(a);mp[a]=1;tr[1]=0;
    int d=0;
    while (mp[b]==0&&dem<1000000)
    {
        node k=q.top();
        q.pop();
        d++;
        int u,v;
        node s;
        u=D[mp[k]].first;
        v=D[mp[k]].second;
        for (l=0;l<4;l++)
        {
            int x=u+X[l];
            int y=v+Y[l];
            s=k;
            if (x>0&&y>0&&x<=n&&y<=n)
            {
                swap(s.A[x][y],s.A[u][v]);
                if (mp[s]==0)
                {
                    q.push(s);
                    dem++;
                    if (dem>1000000) break;
                    mp[s]=dem;
                    tr[dem]=mp[k];
                    D[dem]={x,y};
                }

            }
            if (mp[b]>0||dem>1000000) break;
        }
    }
    int k=mp[b];
    if (k==0) return;
    vector <pair<int,int> > res;
    while (k!=mp[a])
    {
       res.push_back(D[k]);
       k=tr[k];
    }
    cout<<res.size()<<'\n';
    cout<<D[k].first<<' '<<D[k].second<<'\n';
    for (i=res.size()-1;i>=0;i--){
        assert(res[i].first > 0 && res[i].first <= n);
        assert(res[i].second > 0&& res[i].second <= n);
        cout<<res[i].first<<' '<<res[i].second<<'\n';
    }
}
int main()
{
    freopen("sqsubone.inp","r",stdin);
    freopen("sqsubone.out","w",stdout);
    solve();
    return 0;
}