프로그램 명: coci_zmija
제한시간: 1 초
미코는 잘 알려진 Snake 게임 비슷한 게임을 만들고 있다. 이 게임에는 R*S 위에서 뱀이 움직인다. 이 게임의 목적은 모든 사과를 먹는 것이다.
불행히도 미코의 게임은 오리지널 게임과는 다르다.
미코의 게임 규칙은 다음과 같다.
-
오리저널과는 다르게 게임은 화면에 랜덤하게 나타나지 않는다. 대신 게임의 시작시점에 모든 사과의 위치를 안다.
-
게임시작시 뱀은 화면 왼쪽 하단에 위치하고, 오른쪽을 보고 있다.
-
두 개의 버턴 A , B 가 있다.
-
버튼 A 를 누르면 1 칸 전진 한다.
화면 밖으로 나가게되는 경우에는 아무 동작도 하지 않는다.
-
B 버튼을 누르면 뱀은 180 도 방향을 바꾸어서 위로 1 픽셀 움직인다.
-
사과위로 지나간다면 사과는 먹데 꼬리는 길어지지 않는다.
사과를 모두 먹을 수 있는 최소 버튼 수를 구하는 것이 문제이다.
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:
- unlike the original, the apples don’t appear randomly on the screen, but instead you know the
positions of all apples at the beginning of the game
-
at the beginning of the game, the snake is located in the lower left pixel of the screen and is
facing right
-
there are two buttons in the game, denoted with A and B
-
when you press the button A, the snake moves forward by 1 pixel in the direction which it is
currently facing. If that move would cause the snake to go off screen, nothing happens.
-
when you press the button B, the snake moves up by 1 pixel and changes the direction it’s facing
by 180°
-
when the snake moves to a pixel containing an apple, it eats the apple but doesn’t grow like in
the original 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....
출력
7
입력
5 5
.....
J...J
.J.J.
.JJJ.
Z....
출력
15
입력
3 4
...J
....
Z...
출력
5
Clarification of the first example: The shortest sequence of button presses needed for the snake to collect
all the apples is BBAAABB.
출처:coci 2013-2014 contest5 2/6
[질/답]
[제출 현황]
[푼 후(0)]