東京大学 情報理工学系研究科 創造情報学専攻 2022年8月実施 プログラミング 第1問

Author

itsuitsuki

Description (English)

Suppose that we have a maze on a square board with cells. The cell in the -th row and the -th column is denoted by , where and . For example, Figure 1 shows a maze on cells. The cell A is and the cell B is .

The walls composing a maze are denoted as follows. The upper wall of the cell is denoted by , the lower wall is , the left wall is , and the right wall is . For example, the wall p in Figure 2 is and the wall q is .

The layout of walls composing a maze is stored as a character string such as:

0,1,1,0,13,6,8,1

This represents that there are four walls , , , and .

(1) We have a maze on cells. The layout of the walls is stored in file maze1.txt. Draw this maze on the answer sheet so that the layout of the walls will be clearly depicted.

(2) We have a maze on cells. The layout of the walls is stored in file maze2.txt. Count the number of the dead-end cells, which are surrounded with three walls. Write down that number on the answer sheet.

(3) We have a maze on cells. The layout of the walls is stored in file maze3.txt. The start is the cell and the goal is the cell . Count the number of the cells that will be visited when we move from the start to the goal along the shortest path. Write down that number on the answer sheet. Count the start and the goal for one, respectively. Assume that there exists exactly one path between any pair of two cells in the maze.

(4) We have ten mazes on cells. The layout of the walls for each maze is stored in a file from maze10.txt to maze19.txt. Which maze satisfies that there exists exactly one path between any pair of two cells in the maze? Write down the names of all the files in which the layouts of the walls are stored for such a maze.