Deep Sea Navigation
本题没有可用的提交语言。
Description
Rock and his crew are currently searching the deep sea (which can be represented by a $n$ by $m$ grid) for treasure in a shipwreck. They already know where the shipwreck is, but moving through the deep sea is not trivial. To navigate the deep sea, they need to use a submarine that uses special batteries. A battery of power $x$ allows their submarine to move up to $x$ cells in one go. They can only move in the 4 cardinal directions. For example, with a battery of power 2, they could move once to the right, twice to the right, once to the right and once upwards, etc... Once the submarine stops after moving up to $x$ cells, they must replace the battery with a new battery (and cannot reuse the old one).
Additionally, the deep sea is filled with $y$ swarms of mysterious jellyfish which occupy specific locations. These jellyfish don't usually pose a problem, but if Rock and his crew are stationary (such as when they are replacing the battery) in a location with jellyfish, the jellyfish will swarm together and move the submarine to another location. Note that the crew can always replace the battery within the amount of time a jellyfish swarm takes to move them, and if there is a jellyfish swarm at the location they are moved to, they can choose to remain stationary (and get moved again by jellyfish) or move up to $x$ cells using their new battery. Given the starting location of the submarine, the location of the shipwreck, the power of the batteries, and knowledge of the locations and behaviors of the jellyfish swarms, help Rock compute the least number of batteries needed in order to reach the shipwreck.
The first line contains 4 space separate integers: $n$, the number of rows in the sea, $m$, the number of columns in the sea ($2 \leq n * m \leq 10^6$), $x$, the power of the batteries ($1\leq x \leq 10^6$), and $y$, the number of jellyfish swarms ($0\leq y \leq n * m - 2$). The next line contains $a$ and $b$, the starting row and column of the submarine respectively, and $c$ and $d$, the row and column of the shipwreck respectively. Finally, the next $y$ lines each contain four space separated integers: $r_1$, $c_1$, $r_2$, and $c_2$. $r_1$ and $c_1$ represent the row and column of a jellyfish swarm, and $r_2$ and $c_2$ represents a separate location the jellyfish swarm will move the submarine to if it stops in ($r_1$, $c_1$). Note that there are no jellyfish at both the starting location and the shipwreck, and that there cannot be two jellyfish swarms in one location. Additionally, note that all row and column locations are 0-indexed (given location ($r,c$), $0\leq r<n$ and $0\leq c<m$).
Output an integer representing the minimum number of batteries required to reach the shipwreck from the starting location, or -1 if it is not possible to reach the shipwreck.
Input
The first line contains 4 space separate integers: $n$, the number of rows in the sea, $m$, the number of columns in the sea ($2 \leq n * m \leq 10^6$), $x$, the power of the batteries ($1\leq x \leq 10^6$), and $y$, the number of jellyfish swarms ($0\leq y \leq n * m - 2$). The next line contains $a$ and $b$, the starting row and column of the submarine respectively, and $c$ and $d$, the row and column of the shipwreck respectively. Finally, the next $y$ lines each contain four space separated integers: $r_1$, $c_1$, $r_2$, and $c_2$. $r_1$ and $c_1$ represent the row and column of a jellyfish swarm, and $r_2$ and $c_2$ represents a separate location the jellyfish swarm will move the submarine to if it stops in ($r_1$, $c_1$). Note that there are no jellyfish at both the starting location and the shipwreck, and that there cannot be two jellyfish swarms in one location. Additionally, note that all row and column locations are 0-indexed (given location ($r,c$), $0\leq r<n$ and $0\leq c<m$).
Output
Output an integer representing the minimum number of batteries required to reach the shipwreck from the starting location, or -1 if it is not possible to reach the shipwreck.
2 2 1 0
0 0 1 1
4 5 1 3
0 0 0 4
0 3 0 2
1 3 2 2
1 4 2 4
4 5 1 3
0 0 0 4
0 1 0 2
0 2 0 3
0 3 0 4
4 5 1 4
0 0 0 4
0 3 0 2
1 3 2 2
1 4 2 4
2 3 1 4
2
-1
1
6