题意

   有一个n*n的棋盘和m个棋子，每个棋子有一个初始位置和一个目标位置，每次移动只能选择一个棋子移动到他相邻的格子，并且花费一秒钟。请你找出一个移动的方法，使得在10800步内将所有棋子移动到目标位置。

分析

  不是求最少步数！！不是！！题目中保证一定有解，所以很容易想到是构造（场上并没有）

  先读入每个棋子的起始位置，然后将第i个棋子移动到(i,i)位置。然后读入每个棋子的终止位置，然后也将其移动到(i,i)位置，然后正着输出第一个方案，倒着输出第二个方案。

  然后我们怎么考虑将i个棋子移动到(i,i)位置时不冲突。我们先将每个点按照行坐标进行排序，然后行坐标第i大的点移动到第i行，此时每一行最多只有一个点，然后移动列坐标，将点i移动到第i列，显然不会出现冲突。现在每一列最多只有一个点，然后我们将点i移动到第i行。每一步记录一下就可以了。

 

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5  6  7 using namespace std; 8 const int maxn=100+10; 9 struct Node{10     int x,y,id;11     bool operator<(const Node& rhs)const{12         return (x
          
           
            i){45 step=Move(step,node[i].x,node[i].y,i,node[i].y);46 node[i].x=i;47 }48 }49 for(int i=m;i>=1;i--){50 step=Move(step,node[i].x,node[i].y,i,node[i].y);51 node[i].x=i;52 }53 for(int i=1;i<=m;i++){54 step=Move(step,node[i].x,node[i].y,node[i].x,node[i].id);55 node[i].y=node[i].id;56 }57 for(int i=1;i<=m;i++){58 step=Move(step,node[i].x,node[i].y,node[i].id,node[i].y);59 node[i].x=node[i].id;60 }61 return step;62 }63 int main(){64 scanf("%d%d",&n,&m);65 for(int i=1;i<=m;i++){66 scanf("%d%d",&node[i].x,&node[i].y);67 node[i].id=i;68 }69 int step1=solve(0);70 71 for(int i=1;i<=m;i++){72 scanf("%d%d",&node[i].x,&node[i].y);73 node[i].id=i;74 }75 76 int step2=solve(step1);77 printf("%d\n",step2);78 for(int i=1;i<=step1;i++){79 printf("%d %d %d %d\n",anss[i].x,anss[i].y,anst[i].x,anst[i].y);80 }81 for(int i=step2;i>step1;i--){82 printf("%d %d %d %d\n",anst[i].x,anst[i].y,anss[i].x,anss[i].y);83 }84 85 return 0;86 }