问题 4398 --2010-网络赛F-国际日的游行队列

4398: 2010-网络赛F-国际日的游行队列

时间限制: 1 Sec  内存限制: 256 MB
提交: 0  解决: 0
[提交][状态][讨论版][命题人:]

题目描述

有n×n个学生在操场上准备国际日的游行队列。可以认为操场是一个n×m的网格。西北角的坐标是(1,1),东南角的坐标是(n,m)。

在训练时,每个学生必须站在一个直线的交叉点且所有学生必须形成一个n×n的方块。上面的图片显示的是9个学生在3×8的运动场上所形成的图。黑点表示学生。你可以看见9个学生组成3×3的方阵。

          训练过后,学生们会自由散开休息。为了方便他们的教练管理好训练,学生只可以在东西方向移动。当下一次的训练开始,教练会任何位置集合他们再次组成3×3的方阵。当然,学生不可以站到运动场的外边。

         你知道每个学生休息时的坐标,你的任务是计算学生们再次形成n×n的方阵所需移动的最小步数和。

 

输入

  将有多组测试数据给出

 

  对于每一组测试数据:首先在第一行给出两个整数n,m (n<=56, m<=200)

 

  在接下来的 n*n行中,每行将给出两个整数 1<=Xi<=n, 1<=Yi<=m ;表示第ith个学生的坐标是(Xi, Yi)。可能有多个学生站在同一个点。

 

   当n=m=0,数据输入结束。

输出

对于每一组测试数据,用一行输出一个整数,表示学生们再次形成n×n的方阵所需移动的最小步数和。

样例输入

2 168<br/>2 101<br/>1 127<br/>1 105<br/>2 90<br/>0 0<br/>

样例输出

41<br/>

提示

来源

[提交][状态]