Pro.ID22189 TitleHero Title链接http://10.20.2.8/oj/exercise/problem?problem_id=22189 AC0 Submit0 Ratio- 时间&空间限制描述The beautiful princess is caught by the demon again. Super Mario, her lover, has to take the responsibility to be the hero. The princess is incarcerated in a horrific castle which is smelly and full of monsters. She is very scared. Super Mario is very worried about the princess and wants to see the princess as soon as possible. Though he runs fast, he still wants to know how fast it will take to reach the place where the princess is.
The castle is a N*M matrix. Initially Mario and princess are located in different positions. Mario can move up, down, left, right, one step per second. Specially, there are some springs distributed in the castle (Don't ask why, maybe the demon likes to play spring. ^_^). These springs are supernatural and may be used as a tool to help Mario if used properly. Each of the spring has an attribute — spring power which is an integer number actually. When Mario enters a grid where there is a spring whose spring power is k, he will be sprung k grids following the direction he enters the grid in no time.
 -->  -------------> Mario Spring Mario
Figure 1
For example, supposed Mario is in (2, 8), and there is a spring in grid (2, 7) with 5 spring power. If Mario goes left one step, he will be sprung 5 grids left. So the final position of Mario is (2, 2) and the time from (2, 8) to (2, 2) for Mario is just one second.
Note that if Mario is sprung outside the matrix, he will be stopped by the wall of the castle and drop on the grid beside the wall. For example, supposed Mario is in (2, 8), and there is a spring in grid (2, 7) with 10 spring power. If Mario goes left one step, he will just sprung 6 grids left, then stop and drop in grid (2, 1).
Moreover, if the position where Mario will land has a spring, he can be sprung again. That means Mario can be sprung consecutively until he lands on a grid without spring. And only the landing position may affect Mario's action, all grids that Mario passes by when he is sprung have nothing to do with him. For example, supposed Mario is in (2, 8) and there are two grid have springs — (2, 7) and (2, 5), both are 5 spring power. If Mario steps left, he will be sprung to position (2, 2). So the spring in (2, 5) does not work on him.
It is your task to tell Mario the minimum time to reach the princess. 输入Input contains several test cases and is terminated by EOF.
Each case begins with one line containing two integers, n and m ( 3 <= n, m <= 100 ), which are the row number and column number of the castle. Then follows a non-negative integer number k, indicating the number of springs. Then follows k lines, each line has three positive integers -- x, y, and p, x, y is the coordinate of the spring ( 2 <= x <= n-1, 2 <= y <= m-1 ) and p is the spring power described above. These are followed by 2 lines lastly, the first line contains two integers, which represent the coordinate of Mario, and the other line is the coordinate of the princess.
You can assume all of the cases are legal. The initial positions of Mario, princess, and springs are distinct. All of the x coordinates are in the range of [1, n] and all of the y coordinates are in the range of [1, m]. And no spring is next to the wall of the castle. 输出Description The beautiful princess is caught by the demon again. Super Mario, her lover, has to take the responsibility to be the hero. The princess is incarcerated in a horrific castle which is smelly and full of monsters. She is very scared. Super Mario is very worried about the princess and wants to see the princess as soon as possible. Though he runs fast, he still wants to know how fast it will take to reach the place where the princess is.
The castle is a N*M matrix. Initially Mario and princess are located in different positions. Mario can move up, down, left, right, one step per second. Specially, there are some springs distributed in the castle (Don't ask why, maybe the demon likes to play spring. ^_^). These springs are supernatural and may be used as a tool to help Mario if used properly. Each of the spring has an attribute — spring power which is an integer number actually. When Mario enters a grid where there is a spring whose spring power is k, he will be sprung k grids following the direction he enters the grid in no time.
--> -------------> Mario Spring Mario
Figure 1
For example, supposed Mario is in (2, 8), and there is a spring in grid (2, 7) with 5 spring power. If Mario goes left one step, he will be sprung 5 grids left. So the final position of Mario is (2, 2) and the time from (2, 8) to (2, 2) for Mario is just one second.
Note that if Mario is sprung outside the matrix, he will be stopped by the wall of the castle and drop on the grid beside the wall. For example, supposed Mario is in (2, 8), and there is a spring in grid (2, 7) with 10 spring power. If Mario goes left one step, he will just sprung 6 grids left, then stop and drop in grid (2, 1).
Moreover, if the position where Mario will land has a spring, he can be sprung again. That means Mario can be sprung consecutively until he lands on a grid without spring. And only the landing position may affect Mario's action, all grids that Mario passes by when he is sprung have nothing to do with him. For example, supposed Mario is in (2, 8) and there are two grid have springs — (2, 7) and (2, 5), both are 5 spring power. If Mario steps left, he will be sprung to position (2, 2). So the spring in (2, 5) does not work on him.
It is your task to tell Mario the minimum time to reach the princess. Input Input contains several test cases and is terminated by EOF.
Each case begins with one line containing two integers, n and m ( 3 <= n, m <= 100 ), which are the row number and column number of the castle. Then follows a non-negative integer number k, indicating the number of springs. Then follows k lines, each line has three positive integers -- x, y, and p, x, y is the coordinate of the spring ( 2 <= x <= n-1, 2 <= y <= m-1 ) and p is the spring power described above. These are followed by 2 lines lastly, the first line contains two integers, which represent the coordinate of Mario, and the other line is the coordinate of the princess.
You can assume all of the cases are legal. The initial positions of Mario, princess, and springs are distinct. All of the x coordinates are in the range of [1, n] and all of the y coordinates are in the range of [1, m]. And no spring is next to the wall of the castle. Output For each test case, just output one line presenting the minimum time Mario will spend. Mario can not save the princess (Oh, my god *_* but it may happen), just print "Impossible" one line(without quotation marks). Sample Input 10 10
0
2 2
7 8
10 10
1
2 7 5
2 8
1 1
10 10
1
2 7 10
2 8
1 1
10 10
2
2 7 5
2 5 5
2 8
1 1
10 10
4
7 9 2
7 7 2
6 8 2
8 8 2
2 2
7 8 Sample Output 11
3
2
3
Impossible Source 样例输入10 10
0
2 2
7 8
10 10
1
2 7 5
2 8
1 1
10 10
1
2 7 10
2 8
1 1
10 10
2
2 7 5
2 5 5
2 8
1 1
10 10
4
7 9 2
7 7 2
6 8 2
8 8 2
2 2
7 8 样例输出11
3
2
3
Impossible 作者 |
|Archiver|手机版|小黑屋|同和创作矩阵
( 粤ICP备20019636号-1 )
GMT+8, 2025-2-4 15:51 , Processed in 0.017943 second(s), 14 queries .
Powered by Discuz! X3.4 Licensed
© 2001-2017 Comsenz Inc.
