Dragon slayer
Time Limit : 2000/1000ms (Java/Other) Memory Limit : 65536/65536K (Java/Other)
Total Submission(s) : 0 Accepted Submission(s) : 0
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
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 $(x_s+0.5,y_s+0.5)$.
The position of the dragon is $(x_t+0.5,y_t+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 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 $(x_s+0.5,y_s+0.5)$.
The position of the dragon is $(x_t+0.5,y_t+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?
Input
The first line contains an integer $T(T \le 10)$ —the number of test cases.
The first line of each test case contains 3 integers $n,m,K(1 \le n,m,K \le 15)$ —length and width of rectangular area, number of walls
The second line of each test case contains 4 integers $x_s,y_s,x_t,y_t(0 \le x_s,x_t < n,0 \le y_s,y_t < m)$ — the position of the hero and the dragon.
The next $K$ lines , each line contains 4 integers $x_1,y_1,x_2,y_2(0 \le x_1,x_2 \le n,0 \le y_1,y_2 \le m)$ — indicates the location of the two endpoints of the wall, ensuring that $x_1=x_2$ or $y_1=y_2$.
The first line of each test case contains 3 integers $n,m,K(1 \le n,m,K \le 15)$ —length and width of rectangular area, number of walls
The second line of each test case contains 4 integers $x_s,y_s,x_t,y_t(0 \le x_s,x_t < n,0 \le y_s,y_t < m)$ — the position of the hero and the dragon.
The next $K$ lines , each line contains 4 integers $x_1,y_1,x_2,y_2(0 \le x_1,x_2 \le n,0 \le y_1,y_2 \le m)$ — indicates the location of the two endpoints of the wall, ensuring that $x_1=x_2$ or $y_1=y_2$.
Output
For each test case, a line of output contains an integer representing at least the number of times the special ability was required.
Sample Input
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
Sample Output
2 0
Source
2022“杭电杯”中国大学生算法设计超级联赛（1）