Chapter 18. Recursion(2)[Java Basic]

18.E - 미로 탈출

Time Limit: 1s Memory Limit: 128MB

 

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

........

........

........S

 

AMPLE OUTPUT

14

 

18.F - 게임 : Knight의 경로 (난이도:고급)

Time Limit: 1s Memory Limit: 128MB

 

DESCRIPTION

Knight's Tour는 고대 퍼즐이다. 목적은 Knigt를 움직여 체스보드에 어떤 위치에서든 출발하여 모든 위치를 향해 가는 것이다. Knight는 오직 L모양으로 움직일 수 만 있다(직진 두번 좌,우 중 한번) 

 

이 문제에서는 시작위치는 0,0으로 고정되어 있다. 우리가 할 일은 서로 다른 map의 시작위치에서 knight tour가 가능한지 확인하는 일이다.

가능하면 True

불가능하면 False

를 출력하시오.

 

(Game: Knight’s Tour) The Knight’s Tour is an ancient puzzle. The objective is to move a knight, starting from any square on a chessboard, to every other square once, as shown in Figure 18.15a. Note that the knight makes only L-shaped moves (two spaces in one direction and one space in a perpendicular direction). As shown in Figure 18.15b, the knight can move to eight squares. Write a program that displays the moves for the knight, as shown in Figure 18.15c. When you click a cell, the knight is placed at the cell. This cell will be starting point for the knight. Clicking the Solve button to display the path for a solution.

INPUT

Line 1 : a b ( a : 행, b : 열 / 판의 크기, 0 < a,b < 10)

 

OUTPUT

Line 1 : Knight's tour 가능 여부(True, False)

 

SAMPLE INPUT

8 8

 

SAMPLE OUTPUT

True

 

HINT

(Hint: A brute-force approach for this problem is to move the knight from one square to another available square arbitrarily. Using such an approach, your program will take a long time to finish. A better approach is to employ some heuristics. A knight has two, three, four, six, or eight possible moves, depending on its location. Intuitively, you should attempt to move the knight to the least accessible squares first and leave those more accessible squares open, so there will be a better chance of success at the end of the search.)

 

 

18.G - 재귀 피라미드

Time Limit: 10s Memory Limit: 128MB

 

 

DESCRIPTION

다음 샘플 예제를 보고 재귀함수를 이용해 피라미드를 출력하세요

 

INPUT

첫째 줄에 N이 주어진다. N은 항상 3*2^k 수이다. (3, 6, 12, 24, 48, ...) (0<=k<=10)

 

OUTPUT

첫째 줄부터 N번째 줄까지 별을 출력한다.

 

SAMPLE INPUT

12

 

SAMPLE OUTPUT