题目概述

$n\times n(n\le 50)$ 的网格上有 $m(m\le n)$ 个方块，现在要把 $m$ 个方块归位，移动过程中不能碰到其他方块。求一种方案使得步数不超过 $10800$ 。

解题报告

思维江僵化，看到 $50$ 就写了IDA*，然后果断T了。其实是道构造题。

题解说的好像是先把方块移动到对角线上，然后搞来搞去……英语太差了没看懂。

看了某个AC代码发现一种很精妙的做法：先将方块起始位置排序，然后把排序后的第 $i$ 个点移动到 $(i,ID_i)$ 其中 $ID_i$ 表示第 $i$ 个点原来的编号，移动时需要按照坐标顺序，这样就可以防止碰到其他方块。然后也将方块终止位置执行同样的操作。

做完这些操作最多需要 $2nm$ 的步数，而且让所有方块都和新的终止位置在同一列上，只需要 $nm$ 步将所有方块移动到新的终止位置上就好了！

示例程序

#include<cstdio>
#include<algorithm>
#define fr first
#define sc second
#define mp make_pair
using namespace std;
const int maxm=50,maxk=10800;

int n,m;struct data {int x,y,ID;} a[maxm+5],b[maxm+5];
int top[3];pair<pair<int,int>, pair<int,int> > stk[3][maxk+5];

inline bool Pcmp(const data &a,const data &b) {return a.x<b.x||a.x==b.x&&a.y<b.y;}
inline bool Icmp(const data &a,const data &b) {return a.ID<b.ID;}
inline void Move(data *a,int ID){
    for (int i=1;i<=m;i++) while (a[i].x>i) stk[ID][++top[ID]]=mp(mp(a[i].x,a[i].y),mp(a[i].x-1,a[i].y)),a[i].x--;
    for (int i=m;i>=1;i--) while (a[i].x<i) stk[ID][++top[ID]]=mp(mp(a[i].x,a[i].y),mp(a[i].x+1,a[i].y)),a[i].x++;
    for (int i=1;i<=m;i++) while (a[i].y>a[i].ID) stk[ID][++top[ID]]=mp(mp(a[i].x,a[i].y),mp(a[i].x,a[i].y-1)),a[i].y--;
    for (int i=m;i>=1;i--) while (a[i].y<a[i].ID) stk[ID][++top[ID]]=mp(mp(a[i].x,a[i].y),mp(a[i].x,a[i].y+1)),a[i].y++;
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++) scanf("%d%d",&a[i].x,&a[i].y),a[i].ID=i;sort(a+1,a+1+m,Pcmp);
    for (int i=1;i<=m;i++) scanf("%d%d",&b[i].x,&b[i].y),b[i].ID=i;sort(b+1,b+1+m,Pcmp);
    Move(a,0);Move(b,1);sort(a+1,a+1+m,Icmp);sort(b+1,b+1+m,Icmp);
    for (int i=1;i<=m;i++){
        while (a[i].x>b[i].x) stk[2][++top[2]]=mp(mp(a[i].x,a[i].y),mp(a[i].x-1,a[i].y)),a[i].x--;
        while (a[i].x<b[i].x) stk[2][++top[2]]=mp(mp(a[i].x,a[i].y),mp(a[i].x+1,a[i].y)),a[i].x++;
    }
    printf("%d\n",top[0]+top[1]+top[2]);
    for (int i=1;i<=top[0];i++) printf("%d %d %d %d\n",stk[0][i].fr.fr,stk[0][i].fr.sc,stk[0][i].sc.fr,stk[0][i].sc.sc);
    for (int i=1;i<=top[2];i++) printf("%d %d %d %d\n",stk[2][i].fr.fr,stk[2][i].fr.sc,stk[2][i].sc.fr,stk[2][i].sc.sc);
    for (int i=top[1];i>=1;i--) printf("%d %d %d %d\n",stk[1][i].sc.fr,stk[1][i].sc.sc,stk[1][i].fr.fr,stk[1][i].fr.sc);
    return 0;
}