CF1797A.Li Hua and Maze
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
There is a rectangular maze of size n×m . Denote (r,c) as the cell on the r -th row from the top and the c -th column from the left. Two cells are adjacent if they share an edge. A path is a sequence of adjacent empty cells.
Each cell is initially empty. Li Hua can choose some cells (except (x1,y1) and (x2,y2) ) and place an obstacle in each of them. He wants to know the minimum number of obstacles needed to be placed so that there isn't a path from (x1,y1) to (x2,y2) .
Suppose you were Li Hua, please solve this problem.
输入格式
The first line contains the single integer t ( 1≤t≤500 ) — the number of test cases.
The first line of each test case contains two integers n,m ( 4≤n,m≤109 ) — the size of the maze.
The second line of each test case contains four integers x1,y1,x2,y2 ( 1≤x1,x2≤n,1≤y1,y2≤m ) — the coordinates of the start and the end.
It is guaranteed that ∣x1−x2∣+∣y1−y2∣≥2 .
输出格式
For each test case print the minimum number of obstacles you need to put on the field so that there is no path from (x1,y1) to (x2,y2) .
输入输出样例
输入#1
3 4 4 2 2 3 3 6 7 1 1 2 3 9 9 5 1 3 6
输出#1
4 2 3
说明/提示
In test case 1, you can put obstacles on (1,3),(2,3),(3,2),(4,2) . Then the path from (2,2) to (3,3) will not exist.