6539: Dragon slayer
内存限制：64 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：22
解决：14
题目描述
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 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.
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样例输出 复制
2
0