Responsive image

问题 C: 迷宫(思维)

问题 C: 迷宫(思维)

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

题目描述

有一个大小为n×m的长方形迷宫。用(r,c)表示从上往下第r行和从左往右第c列的单元。

每个格子最初都是空的。小鸿可以选择一些单元格(除了(x1,y1)和(x2,y2)),并在选择的单元格中放置一个障碍物。他想知道需要放置的最小障碍物数量,以便没有从(x1,y1)到(x2,y2)的路径(只能上下左右四个方向移动,不能斜着走)。

假设你是小鸿,请解决这个问题。

输入描述

第一行包含单个整数 t1≤t≤500 )--测试案例的数量。

每个测试案例的第一行包含两个整数n,m (4≤n,m≤109 ) --迷宫的大小。

每个测试案例的第二行包含四个整数x1,y1,x2,y2 (1≤x1,x2≤n,1≤y1,y2≤m ) --起点和终点的坐标。

可以保证|x1-x2|+|y1-y2|≥2

输出描述

对于每个测试案例,输出你需要在场地上放置的最小数量的障碍物,以便没有从(x1,y1)到(x2,y2)的路径。

样例输入

3
4 4
2 2 3 3
6 7
1 1 2 3
9 9
5 1 3 6

样例输出

4
2
3

提示

在测试案例1中,你可以在(1,3), (2,3), (3,2), (4,2)上设置障碍。那么从(2,2)到(3,3)的路径将不存在。


[提交][状态]
ACM算法攻关部