1419-铺设电缆


    内存限制:64MB 时间限制:1000ms 特判: No

    通过数:1 提交数:2 难度:4


题目描述:

在实际工程中,铺设电缆等设施时,既考虑障碍物的问题,又要考虑造价最低。随着电子设备的普及,工程中需要大量的电路板。每个电路板上有很多线路,我们在设计电路时,尽可能地节约成本,如果一个电路板省下一分钱,也将是一笔很大的财富。布线问题就是在m×n的方格阵列中,指定一个方格的中点a,另一个方格的中点b,问题要求找出ab的最短布线方案。布线时只能沿直线或直角,不能走斜线。为了避免线路相交,已布过线的方格做了封锁标记(灰色),其他线路不允许穿过被封锁的方格。


输入描述:

第一行是一个整型数C(C<100)表示共有C组测试数据。
每组测试数据第一行输入方格阵列m,n(1<=m,n<=50)。
接下来输入障碍物坐标行列x,y,输入0 0结束(1<=x,y <=50)。
最后两行,输入起点坐标a.x,a.y(1<=a.x,a.y <=50),
输入终点坐标b.x,b.y(1<=b.x,b.y <=50)。

输出描述:

对于每一组输入,输出满足条件的最短距离,若任务无法达成,则输出“-1”。
每组的输出占一行。

样例输入:

2
5 6
1 6
2 3
3 4
3 5
5 1
0 0
2 1
4 6
6 7
1 5
2 3
3 3
3 5
3 6
4 3
5 6
6 4
6 5
6 6
0 0
3 1
6 7

样例输出:

7
11

提示:


上传者:rainflychxy

书中题目链接,请点击上面链接访问!

公告

    欢迎使用NYOJ2.0!