| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 9196 | Territory Expansion |
|
| 9276 | Can you escape? |
|
Description
There are many countries on a map. Each of them has a unique ID, which is a positive integer. All of them want to expand their territories. A country can expand its territory if its neighboring land (up, down, left, and right) has not been occupied by any other countries. The expansion speeds are the same for all countries. (We may consider that all countries simultaneously perform one expansion move at a time.) If two or more countries want to occupy the same land, the country with the smaller ID can occupy the land. The expansion stops if no changes of the map can be made.
Input
The input file begins with an integer T (1 < T < 1000), indicating the number of test cases. Each test case begins with three integers N, M, and K (0 < N < 300, 0 < M < 300, K
Output
For each test case, output the final area (number of lands) of each county, ordered by the country’s ID (from small to large). Print a blank after each case.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given a map, how fast can you get the two keys and then escape?
The map is a 2-dimensional grid of squares, each square is either free or filled with a wall. You can move between adjacent free squares vertically or horizontally, diagonal movement is not allowed. You may not go across walls. You have to get the two keys first and then you can go to the door. Notice that before you get the both keys, you can not pass the door.
Hint: Go to the nearest key first is not always the best choice, see the sample test cases.
Input
The input consists of several maps. Each map begins with a line containing two integer numbers R and C (1 <= R, C <= 1000) specifying the map size. Then there are R lines each containing C characters. Each character is one of the following:
s : Your start position.
. : A free square that you can move.
k : The position of the key.
w : The wall.
d : The door.
There are exactly two keys and exactly one door.
There is one blank line after each map. The input is terminated by two zeros in place of the map size.
Output
For each map, print one line containing the sentence "Escape in S steps.", where S is the smallest possible number of step to reach the door. If no way to reach the door, output the string "No solution." instead. One step is defined as a movement between two adjacent squares. Grabbing a key or unlocking a door does not count as a step.