Dungeon Wall#3544
In 2337, people are bored with daily life and have a strong desire for extraordinary experiences. These days, "Dungeon Adventure" is one of the hottest attractions, where brave adventurers risk their lives to defeat evil monsters and save the world.
You are the manager of such a dungeon. Recently, you have received many complaints from soldiers who frequently enter your dungeon; they say your dungeon is too easy and they do not want to return. You are considering making your dungeon more challenging by increasing the distance between the entrance and the exit so that more monsters can approach the adventurers.
Your dungeon is a rectangle with width and height . The dungeon is a grid of W \times H square rooms, each of size 1 \times 1. The southwest corner of the dungeon is at , and the northeast corner is at (W, H). The dungeon is surrounded by outer walls, and there may be additional internal walls to prevent adventurers from moving directly to the exit. Each wall is parallel to either the -axis or the -axis, and both ends of each wall are at integer coordinates. An adventurer can move from one room to an adjacent room vertically or horizontally if there is no wall between them.
You would like to add some walls to make the shortest path between the entrance and the exit longer. However, due to financial constraints, you can build at most one wall of unit length. The new wall must also comply with the constraints stated above, and you must ensure there is still at least one path from the entrance to the exit.
You are wondering where to place the new wall to maximize the minimum number of steps required between the entrance and the exit. Can you figure it out?
The first line contains three integers , , and (1 \leq W, H \leq 50, 0 \leq N \leq 1000), separated by spaces.
The next lines each describe an internal wall. Each line contains four integers sx_i, sy_i, dx_i, dy_i—the endpoints of the -th wall, running from (sx_i, sy_i) to (dx_i, dy_i) (inclusive).
The last two lines describe the entrance and exit. The first of these lines contains two integers and ; the second contains two integers and . The entrance is at the room whose southwest corner is (ix, iy) and the exit is at the room whose southwest corner is (ox, oy).
Print the maximum possible increase in the minimum number of required steps between the entrance and the exit by adding a single wall. If no suitable place for a new wall exists, print 0.
Example 1