|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|1 초||32 MB||10||7||6||66.667%|
Mirko is making a clone of the popular computer game "Snake". In the game, you control the movement of a snake on a screen with dimensions of R · S pixels. The objective of the game is to collect all the apples.
Unfortunately, Mirko’s implementation isn’t that great and the gameplay is different than the original. Here is a description of Mirko’s game:
You have the following task: for given positions of apples at the beginning of the game, determine the smallest number of button presses it takes for the snake to collect all the apples.
The first line of input contains the integers R and S (2 ≤ R, S ≤ 1 000), the height and width of the screen.
Each of the following R lines contains exactly S characters. These characters represent the content of the screen. Pixels with apples on them are denoted with ’J’ and empty pixels are denoted with ’.’.
The lower left corner contains the character ’Z’ that represents the snake in its initial position.
The first and only line of output must contain the required minimal number of button presses.
5 5 ...J. ..... J..J. J.... Z....
5 5 ..... J...J .J.J. .JJJ. Z....
3 4 ...J .... Z...
Clarification of the first example: The shortest sequence of button presses needed for the snake to collect all the apples is BBAAABB.