ZOJ Problem Set - 1479
In a room with n rows and m columns, Dweep and her child is separated by some laser beams and obstacles. Dweep has to manage to make through the laser beams to rescue her child. She can pour some water on herself and walk through a cell with laser beams, and arrive at a cell without laser beams, when her body is dry again. Dweep can walk in eight directions. Dweep can only pour water in a cell without laser beams, so she is not able to walk over two continuous cells with laser beams. Laser beam stops at obstacle or other laser generator.
It's your turn to tell the minimum number of times Dweep has to pour water onto herself in order to reach the cell of her child.
There are multiple cases in the input, separated with blank lines. Please process to the end of file.
The first line of each case contains integers n and m (1 <= n, m <= 20).
The second line is the place of Dweep and her child, in the form (row, col).
The third line is an integer k, the sum of laser generators and obstacles.
k lines followed, in the form (row, col, type). there are five possible values for type:
u - laser generator facing north
One number for each case, the minimum number of times Dweep gets wet. If there is no solution, print -1.
Author: DU, Peng
Source: ZOJ Monthly, January 2003