SHOW:
|
|
- or go back to the newest paste.
| 1 | #include <bits/stdc++.h> | |
| 2 | using namespace std; | |
| 3 | const int X[4]={1,-1,0,0};
| |
| 4 | const int Y[4]={0,0,1,-1};
| |
| 5 | int n,tr[1000002]; | |
| 6 | pair <int,int> D[1000002]; | |
| 7 | struct node{
| |
| 8 | int A[12][12]; | |
| 9 | bool operator < (const node&a) | |
| 10 | const | |
| 11 | {
| |
| 12 | for (int i=1;i<=10;i++) | |
| 13 | for (int j=1;j<=10;j++) | |
| 14 | if (A[i][j]!=a.A[i][j]) return (A[i][j]<a.A[i][j]); | |
| 15 | return false; | |
| 16 | } | |
| 17 | }; | |
| 18 | map <node,int> mp; | |
| 19 | node a,b; | |
| 20 | struct sosanh{
| |
| 21 | bool operator() (const node &s,const node &t) | |
| 22 | const | |
| 23 | {
| |
| 24 | int dems=0;int demt=0; | |
| 25 | for (int i=1;i<=10;i++) | |
| 26 | for (int j=1;j<=10;j++) | |
| 27 | if (s.A[i][j]==b.A[i][j]) dems++; | |
| 28 | for (int i=1;i<=10;i++) | |
| 29 | for (int j=1;j<=10;j++) | |
| 30 | if (t.A[i][j]==b.A[i][j]) demt++; | |
| 31 | return (dems<demt); | |
| 32 | } | |
| 33 | }; | |
| 34 | ||
| 35 | void doc() | |
| 36 | {
| |
| 37 | int i,j; | |
| 38 | cin>>n; | |
| 39 | for (i=1;i<=n;i++) | |
| 40 | for (j=1;j<=n;j++) | |
| 41 | {
| |
| 42 | int x;cin>>x; | |
| 43 | a.A[i][j]=x; | |
| 44 | if (x==0) D[1]={i,j};
| |
| 45 | } | |
| 46 | for (i=1;i<=n;i++) | |
| 47 | for (j=1;j<=n;j++) | |
| 48 | {
| |
| 49 | int x; | |
| 50 | cin>>x; | |
| 51 | b.A[i][j]=x; | |
| 52 | } | |
| 53 | } | |
| 54 | void solve() | |
| 55 | {
| |
| 56 | doc(); | |
| 57 | int i,j,l; | |
| 58 | priority_queue <node,vector <node>,sosanh > q; | |
| 59 | int dem=1; | |
| 60 | q.push(a);mp[a]=1;tr[1]=0; | |
| 61 | int d=0; | |
| 62 | while (mp[b]==0&&dem<1000000) | |
| 63 | {
| |
| 64 | node k=q.top(); | |
| 65 | q.pop(); | |
| 66 | d++; | |
| 67 | int u,v; | |
| 68 | node s; | |
| 69 | u=D[mp[k]].first; | |
| 70 | v=D[mp[k]].second; | |
| 71 | for (l=0;l<4;l++) | |
| 72 | {
| |
| 73 | int x=u+X[l]; | |
| 74 | int y=v+Y[l]; | |
| 75 | s=k; | |
| 76 | if (x>0&&y>0&&x<=n&&y<=n) | |
| 77 | {
| |
| 78 | swap(s.A[x][y],s.A[u][v]); | |
| 79 | if (mp[s]==0) | |
| 80 | {
| |
| 81 | q.push(s); | |
| 82 | dem++; | |
| 83 | if (dem>1000000) break; | |
| 84 | mp[s]=dem; | |
| 85 | tr[dem]=mp[k]; | |
| 86 | D[dem]={x,y};
| |
| 87 | } | |
| 88 | ||
| 89 | } | |
| 90 | if (mp[b]>0||dem>1000000) break; | |
| 91 | } | |
| 92 | } | |
| 93 | int k=mp[b]; | |
| 94 | if (k==0) return; | |
| 95 | vector <pair<int,int> > res; | |
| 96 | while (k!=mp[a]) | |
| 97 | {
| |
| 98 | res.push_back(D[k]); | |
| 99 | k=tr[k]; | |
| 100 | } | |
| 101 | cout<<res.size()<<'\n'; | |
| 102 | cout<<D[k].first<<' '<<D[k].second<<'\n'; | |
| 103 | for (i=res.size()-1;i>=0;i--){
| |
| 104 | assert(res[i].first > 0 && res[i].first <= n); | |
| 105 | assert(res[i].second > 0&& res[i].second <= n); | |
| 106 | cout<<res[i].first<<' '<<res[i].second<<'\n'; | |
| 107 | } | |
| 108 | } | |
| 109 | int main() | |
| 110 | {
| |
| 111 | freopen("sqsubone.inp","r",stdin);
| |
| 112 | freopen("sqsubone.out","w",stdout);
| |
| 113 | solve(); | |
| 114 | return 0; | |
| 115 | } |
