[JAVA] 미로 탈출

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

14

SOURCE

JAVA2015 PE18.26