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

标签：

• Tokyo-University
• Breadth-First-Search
• Programming

Author

itsuitsuki

Description

Suppose that we have a maze on a square board with $m \times m$ cells. The cell in the $i$-th row and the $j$-th column is denoted by $(i, j)$, where $0 \le i \le m-1$ and $0 \le j \le m-1$. For example, Figure 1 shows a maze on $6 \times 6$ cells. The cell A is $(0,0)$ and the cell B is $(2,5)$.

When a sequence of numbers is stored, we store a character string in a file as follows.

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

This denotes the sequence of numbers where the 0th number is 2, the 1st number is 0, the 2nd number is 13, ... All the elements in a sequence are integers more than or equal to zero.

(1) A sequence of numbers {$s_k$} is stored in file sequence.txt. Write down the 216-th element $s_{216}$ in that sequence on the answer sheet. Furthermore, write down the maximum number among the elements in that sequence on the answer sheet.

(2) Make a maze on $40 \times 40$ cells in accordance with the following instructions. A sequence of numbers $\{p_k\}$ is stored in file p.txt. Its elements are either 0, 1, 2, or 3.

1. Put walls along the outer limits of the maze.
2. For every pair of $i$ and $j$, where $1 \leq i \leq 39$ and $1 \leq j \leq 39$,
   • put the upper wall for cell $(i,j)$ when $p_s$ is 0,
   • put the left wall for cell $(i,j)$ when $p_s$ is 1,
   • put the lower wall for cell $(i-1, j-1)$ when $p_s$ is 2,
   • put the right wall for cell $(i-1, j-1)$ when $p_s$ is 3.

Here, $s = i \times 40 + j$ and $p_s$ is the $s$-th element of the sequence of numbers $\{p_k\}$. Note that, for different pairs of $i$ and $j$, the same wall may be put.

(2-a) Write down on the answer sheet the existence of the upper, lower, left, and right walls for cells $(5, 25)$, $(20, 20)$, and $(30, 33)$ in this maze.

(2-b) Write down on the answer sheet the number of the L-shaped corner cells in this maze. A cell is a L-shaped corner cell when it is surrounded with exactly two walls directly jointed to form L-shape.

(3) Make a maze on $40 \times 40$ cells in accordance with the following instructions. The start is cell $(0,0)$ and the goal is cell $(39,27)$. A cell surrounded with four walls is called a closed cell.

1. Put the upper, lower, left, and right walls for all the cells so that all the cells are closed cells.

2. Set the current position to the start cell.

3. Select a closed cell N in the maze among the upper, lower, left, and right cells adjacent to the current position. Then remove the wall separating the selected cell N and the current position. Move the current position to that cell N. Repeat this again.

   When selecting the cell N, refer to the sequence of numbers $\{n_k\}$ stored in file neighbor.txt. The elements of this sequence is either 0, 1, 2, or 3.

   Suppose that the current position is $(i,j)$. Let $n_s$ be the $s$-th element of the sequence $\{n_k\}$. For given $s$, when $n_s$ is 0, select the upper cell of the cell $(i,j)$. When it is 1, select the left cell. When it is 2, select the lower cell. When it is 3, select the right cell for N, respectively. Here, $s = i+j+h$. Choose $h$ for selecting N. $h$ is an integer more than or equal to zero and also $h$ is the minimum integer such that a closed cell is selected for N.

   When no cell is selectable for N, select a cell C. The cell C must not be a closed cell. Furthermore, at least one adjacent cell to C must be a closed cell. Move the current position to that cell C. When a necessary element of the sequence $\{n_k\}$ does not exist, select a cell C and move the current position to that cell C.

   When selecting the cell C, refer to the sequence of numbers $\{c_k\}$ stored in file cell.txt. Its elements are integers less than 40 and more than or equal to zero.

   Suppose that the current position is $(i,j)$. Select a cell $(c_t, c_{t+1})$ such that $t$ is minimum among the cells satisfying the requirements for C. Here, $t = 2(i+j+h)$ and $h$ is an integer more than or equal to zero.

   When no cell is selectable for C, the maze is completed. When a necessary element of the sequence $\{c_k\}$ does not exist, the maze is also completed.

(3-a) Write down on the answer sheet the existence of the upper, lower, left, and right walls for cells $(5, 25)$, $(20, 20)$, and $(30, 33)$ in this maze.

(3-b) Write down on the answer sheet the number of the L-shaped corner cells in this maze. A cell is a L-shaped corner cell when it is surrounded with exactly two walls directly jointed to form L-shape.

(3-c) Find the longest straight passages in this maze and write their length down on the answer sheet. Furthermore, write down the number of such longest passages on the answer sheet. For example, the path between cells $(0, 1)$ and $(4, 1)$ in Figure 1 is a straight passage and its length is 5, which is the number of its cells. For the maze in Figure 1, a passage with length 5 is the longest and there are two such passages.

(3-d) We can reach the goal of this maze when proceeding through the maze by always keeping one wall on the left-hand side in the direction of the move. Write down on the answer sheet the number of the cells visited on the way to the goal. When the same cell is visited twice, that cell is counted only once. Include the start and the goal cells in the cells visited on the way. At first, the upper wall of the start cell is on the left-hand side in the direction of the move.

题目描述

考虑 $m\times m$ 方格迷宫，格 $(i,j)$ 满足 $0\le i,j\le m-1$。图 1 的 $6\times6$ 示例中 A 为 $(0,0)$，B 为 $(2,5)$。非负整数序列以逗号分隔存入文件，例如

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

表示第 0 个元素为 2、第 1 个为 0、第 2 个为 13，依此类推。

1. sequence.txt 存有序列 $\{s_k\}$。写出 $s_{216}$ 及整个序列最大值。

2. 按下列规则构造 $40\times40$ 迷宫。p.txt 中序列 $\{p_k\}$ 的元素只可能是 0、1、2、3。

   1. 沿迷宫外边界设置墙。
   2. 对每个 $1\le i,j\le39$，令 $s=i\times40+j$：
      • $p_s=0$：设置格 $(i,j)$ 的上墙；
      • $p_s=1$：设置格 $(i,j)$ 的左墙；
      • $p_s=2$：设置格 $(i-1,j-1)$ 的下墙；
      • $p_s=3$：设置格 $(i-1,j-1)$ 的右墙。

   不同 $(i,j)$ 可能重复设置同一堵墙。

   1. 对格 $(5,25),(20,20),(30,33)$，分别写出上、下、左、右墙是否存在。
   2. 统计 L 形拐角格数量。其定义是恰有两堵墙，且两墙直接相连成 L 形。

3. 再按以下规则构造另一个 $40\times40$ 迷宫，起点 $(0,0)$，终点 $(39,27)$。四面有墙的格称为“封闭格”。

   1. 初始给所有格设置四面墙，使其全为封闭格。
   2. 当前格设为起点。
   3. 在当前格的上、下、左、右相邻格中选择一个封闭格 N，拆除当前格与 N 间的墙，移动到 N，并重复。

   选择 N 时使用 neighbor.txt 的序列 $\{n_k\}$，元素为 0、1、2、3。若当前格为 $(i,j)$，令 $s=i+j+h$，分别以 $n_s=0,1,2,3$ 表示选择上、左、下、右相邻格；取使所选 N 为封闭格的最小非负整数 $h$。

   若没有可选 N，或所需 $n_s$ 不存在，则选择一个格 C：C 自身不是封闭格，且至少有一个相邻格仍是封闭格，然后把当前位置移到 C。选择 C 使用 cell.txt 的序列 $\{c_k\}$，其中 $0\le c_k<40$。对当前格 $(i,j)$，在 $t=2(i+j+h)$、$h\ge0$ 中取使 $(c_t,c_{t+1})$ 满足 C 条件的最小 $t$。若没有可选 C 或所需 $c_k$ 不存在，则迷宫构造完成。

   1. 对 $(5,25),(20,20),(30,33)$ 分别写出四面墙是否存在。
   2. 统计 L 形拐角格数量。
   3. 找出最长直通道，写出其长度及达到该长度的通道数。通道长度按包含格数计；例如图 1 从 $(0,1)$ 到 $(4,1)$ 长度为 5，该示例最长长度为 5，共两条。
   4. 采用左手贴墙法从起点走到终点。统计途中访问过的不同格数量，同一格重复经过只计一次，包含起、终点。开始时，起点的上墙位于行进方向左侧。

Kai

The sample data files are here.