4439 - 미로 탈출

Time Limit: 1s Memory Limit: 128MB

Submissions: 124 Solved: 41

Description

Top-Left 모서리에서 Bottom-Right 모서리까지 장애물을 피해서 이동하는데 필요한 최소 이동횟수를 구하라.

8*8 판

. 길

X 장애물

(Create a maze) Write a program that will find a path in a maze, as shown in Figure 18.13a. The maze is represented by an 8 * 8 board. The path must meet the following conditions:

The path is between the upper-left corner cell and the lower-right corner cell in the maze.
The program enables the user to place or remove a mark on a cell. A path consists of adjacent unmarked cells. Two cells are said to be adjacent if they are horizontal or vertical neighbors, but not if they are diagonal neighbors.
The path does not contain cells that form a square. The path in Figure 18.13b, for example, does not meet this condition. (The condition makes a path easy to identify on the board.)

Input

Line 1 ~ 8 : 한 줄당 8개의 문자로 이루어진 미로 줄

Output

Line 1 : 최단거리

Sample Input

........
xxx.....
..x....x
..x...x.
...xx..x
........
........
........

Sample Output

Source

JAVA2015 PE18.26