Li Hua and Maze (Codeforces 1797A)
Tags: Greedy, flows

There is a rectangular maze of size $$$n\times 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 $$$(x_1, y_1)$$$ and $$$(x_2, y_2)$$$) 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 $$$(x_1, y_1)$$$ to $$$(x_2, y_2)$$$.Suppose you were Li Hua, please solve this problem.

Input: The first line contains the single integer $$$t$$$ ($$$1 \le t \le 500$$$) — the number of test cases.The first line of each test case contains two integers $$$n,m$$$ ($$$4\le n,m\le 10^9$$$) — the size of the maze.The second line of each test case contains four integers $$$x_1,y_1,x_2,y_2$$$ ($$$1\le x_1,x_2\le n, 1\le y_1,y_2\le m$$$) — the coordinates of the start and the end.It is guaranteed that $$$|x_1-x_2|+|y_1-y_2|\ge 2$$$.

Output: For each test case print the minimum number of obstacles you need to put on the field so that there is no path from $$$(x_1, y_1)$$$ to $$$(x_2, y_2)$$$.

Note: 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.  

Sample Inputs:
3
4 4
2 2 3 3
6 7
1 1 2 3
9 9
5 1 3 6

Sample Outputs:
4
2
3

Solution (Python):
t = int(input())
for _ in range(t):
    (n, m) = map(int, input().split())
    (x1, y1, x2, y2) = map(int, input().split())

    def f(x, y):
        if (x == 1 or x == n) and (y == 1 or y == m):
            return 2
        if x == 1 or x == n or y == 1 or (y == m):
            return 3
        return 4
    print(min(f(x1, y1), f(x2, y2)))

Solution (Python):
""""""
t = int(input())
string_input = [[]] * t
for i in range(t):
    string_input[i] = input().split()
    string_input[i].extend(input().split())
for i in range(t):
    lst = string_input[i]
    (n, m, x1, y1, x2, y2) = (int(lst[0]), int(lst[1]), int(lst[2]), int(lst[3]), int(lst[4]), int(lst[5]))
    if x1 == 1 and y1 == 1 or (x1 == 1 and y1 == m) or (x1 == n and y1 == 1) or (x1 == n and y1 == m) or (x2 == 1 and y2 == 1) or (x2 == 1 and y2 == m) or (x2 == n and y2 == 1) or (x2 == n and y2 == m):
        print(2)
    elif x1 == 1 and 1 < y1 < m or (x1 == n and 1 < y1 < m) or (1 < x1 < n and y1 == 1) or (1 < x1 < n and y1 == m) or (x2 == 1 and 1 < y2 < m) or (x2 == n and 1 < y2 < m) or (1 < x2 < n and y2 == 1) or (1 < x2 < n and y2 == m):
        print(3)
    else:
        print(4)

Solution (Python):
k = int(input())
for i in range(k):
    (n, m) = map(int, input().split())
    (x1, y1, x2, y2) = map(int, input().split())
    p = q = 4
    if x1 == 1:
        p -= 1
    if y1 == 1:
        p -= 1
    if x1 == n:
        p -= 1
    if y1 == m:
        p -= 1
    if x2 == 1:
        q -= 1
    if y2 == 1:
        q -= 1
    if x2 == n:
        q -= 1
    if y2 == m:
        q -= 1
    print(min(p, q))