\(5^{th}\) round, January \(17^{th}\) 2015
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 \cdot 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 offscreen, 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.

생성자가 기록되지 않았습니다.

출처 COCI 2014/2015 Contest 5