题目描述
Long, long ago, the dragon captured the princess. In order to save the princess, the hero entered the
dragon’s lair.
The dragon’s lair is a rectangle area of length n and width m. The lower left corner is (0, 0) and the upper
right corner is (n, m).
The position of the hero is (xs + 0.5, ys + 0.5).
The position of the dragon is (xt + 0.5, yt + 0.5).
There are some horizontal or vertical walls in the area. The hero can move in any direction within the
area, but cannot pass through walls, including the ends of walls.
The hero wants to go where the dragon is, but may be blocked by walls.
Fortunately, heroes have access to special abilities, and each use of a special ability can make a wall
disappear forever.
Since using special abilities requires a lot of physical strength, the hero wants to know how many times
special abilities need to be used at least on the premise of being able to reach the position of the evil
dragon?
输入
The first line contains an integer T(T ≤ 10) —the number of test cases.
The first line of each test case contains 3 integers n, m, K(1 ≤ n, m, K ≤ 15) —length and width of
rectangular area, number of walls
The second line of each test case contains 4 integers xs, ys, xt , yt(0 ≤ xs, xt < n, 0 ≤ ys, yt < m) — the
position of the hero and the dragon.
The next K lines , each line contains 4 integers x1, y1, x2, y2(0 ≤ x1, x2 ≤ n, 0 ≤ y1, y2 ≤ m) — indicates the location of the two endpoints of the wall, ensuring that x1 = x2 or y1 = y2.
输出
For each test case, a line of output contains an integer representing at least the number of times the
special ability was required.
2
3 2 2
0 0 2 1
0 1 3 1
1 0 1 2
3 2 2
0 0 2 1
2 1 2 2
1 0 1 1