有一个大小为n×m的长方形迷宫。用(r,c)表示从上往下第r行和从左往右第c列的单元。
每个格子最初都是空的。小鸿可以选择一些单元格（除了（x1,y1）和（x2,y2）），并在选择的单元格中放置一个障碍物。他想知道需要放置的最小障碍物数量，以便没有从（x1,y1）到（x2,y2）的路径（只能上下左右四个方向移动，不能斜着走）。
假设你是小鸿，请解决这个问题。
2853: 迷宫（思维）
时间限制: 1 Sec 内存限制: 256 MB提交: 0 解决: 36
[提交][状态][讨论版][命题人:]
题目描述
输入描述
第一行包含单个整数 t（1≤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。
每个测试案例的第一行包含两个整数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)的路径将不存在。
来源
-
Anything about this OnlineJudge, Please Contact Administrator. Click add QQ
OJ system based on HUSTOJ Project , UI based on Twitter Bootstrap
Copyright 2016 ACM算法攻关部
cnt: 641
关于网站改版