发布时间: 2016年12月3日 16:34 最后更新: 2016年12月3日 16:34 时间限制: 1000ms 内存限制: 65536M
The input consists of several test cases. The first line of each case contains two integers N and M (1 <= N, M <= 100), where N is the height of the map and M is the width of the map. This is followed by N lines each containing M characters representing the map. A '#' represents a rock, a '.' is a free block, 'p' is the starting position of the player, 't' is the position of the treasure, 'n' is the initial position of a non-aggressive monster, and an 'a' stands for the initial position of an aggressive monster.
The cell (i, j) is the j-th cell on the i-th row counting from left to right. The rows are counted from 1 to N starting from the first line of the matrix. We can number all the monsters as 1, 2, 3… according to their initial position, sorting first by row, then by column.
The (n+2)-th line contains an integer p (0 <= p <= 100), which is the total number of monsters (i.e. the total number of 'n's and 'a's in the matrix). It is followed by p lines each specifying a monster's position sequence in the following format: the i-th (1 <= i <= p) line corresponds to monster i, which begins with an integer s (1 <= s <= 100), meaning the length of position sequence. Then s pairs of integers x1, y1, x2, y2, …, xs, ys are followed, separated by blanks. Each pair is a free block in the map, (i.e. a monster never goes to a rock cell).
It is assured that none of the aggressive monsters' initial position is around the player. Two consecutive cases are separated by a blank line. The input is terminated by a line containing a pair of zeros.
For each test case, output the minimum total time required for the player to get the treasure, in seconds. If it's not possible to get the treasure, or the minimum required time is greater than 100 seconds, please print a line just containing the string "impossible". Two consecutive cases should be separated by a blank line.
7 8 #.#####. #.t#..p. #..#.... ..#a.#.# #...##.n .#...... ........ 2 2 4 4 5 4 3 5 8 6 8 5 7 3 3 p#. ##. t.. 0 2 2 #t p# 0 0 0
8 impossible 1