東京大学 情報理工学系研究科 創造情報学専攻 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.

(1)

Split the file at commas and convert the tokens to integers. Indexing begins at zero, so use sequence[216]. The answers are

$$\boxed{s_{216}=46},\qquad \boxed{\max_k s_k=97}.$$

(2-a)

Store each wall once using the wall-coordinate representation of Programming 1. The four candidate coordinates for the instruction at $(i,j)$ are

$$(2i,2j+1),\quad(2i+1,2j),\quad (2i,2j-1),\quad(2i-1,2j),$$

for $p_{40i+j}=0,1,2,3$, respectively. First insert the outer boundary walls, then apply all $39^2$ instructions using a set so duplicate walls have no additional effect.

Here 1 denotes an existing wall and 0 denotes no wall:

Cell	Upper	Lower	Left	Right
$(5,25)$	1	1	0	0
$(20,20)$	1	1	0	1
$(30,33)$	1	1	0	1

(2-b)

A corner must have exactly two walls, excluding the upper–lower and left–right opposite pairs. Testing this condition for all cells gives

$$\boxed{398}.$$

(3-a)

Start with every wall present. At each current cell $(i,j)$, inspect neighbor[i+j+h] in increasing $h$, choosing the first direction leading to an in-bounds closed cell. Removing the shared wall changes both cells' wall counts. If this scan fails, inspect candidate pairs starting at cell[2*(i+j+h)] in increasing $h$, and move to the first nonclosed cell with a closed neighbor. Restart the indices from the new current cell each time.

The resulting walls are:

Cell	Upper	Lower	Left	Right
$(5,25)$	0	1	1	1
$(20,20)$	0	1	0	1
$(30,33)$	0	0	1	0

(3-b)

Apply the same corner test as in (2-b):

$$\boxed{855}.$$

(3-c)

Scan each row into maximal runs joined by open left–right passages and each column into maximal runs joined by open upper–lower passages. A side branch does not interrupt a straight passage. Measure a run by its number of cells, and count every run whose length equals the maximum. The result is

$$\boxed{\text{maximum length}=12,\qquad \text{number of such passages}=1}.$$

(3-d)

The initial direction is east, placing the north wall to the left. At each step try left, forward, right, and backward in that order, and take the first direction with no wall. Keep a set of cells visited and stop upon first reaching $(39,27)$. Counting each cell only once gives

$$\boxed{1243\text{ distinct cells}}.$$

Complete program

Save the following as maze_construction.py and run python maze_construction.py DATA_FOLDER. Wall tuples uniquely identify shared walls; the sequence scans follow the indices specified in the question, without a persistent global sequence cursor.

from pathlib import Path
import sys


def read_numbers(filename):
    return [int(x) for x in Path(filename).read_text().strip().split(',')]


def walls_of(i, j):
    # Upper, lower, left, right.
    return [(2*i,2*j+1), (2*i+2,2*j+1), (2*i+1,2*j), (2*i+1,2*j+2)]


def adjacent(m, cell):
    i,j = cell
    for (di,dj), wall in zip([(-1,0),(1,0),(0,-1),(0,1)],walls_of(i,j)):
        nxt=(i+di,j+dj)
        if 0<=nxt[0]<m and 0<=nxt[1]<m:
            yield nxt,wall


def make_question2(m, p):
    walls = set()
    for i in range(m):
        walls.update([(0,2*i+1),(2*m,2*i+1),(2*i+1,0),(2*i+1,2*m)])
    for i in range(1,m):
        for j in range(1,m):
            choices=[(2*i,2*j+1),(2*i+1,2*j),
                     (2*i,2*j-1),(2*i-1,2*j)]
            walls.add(choices[p[i*m+j]])
    return walls


def make_question3(m, neighbor, cells):
    walls={wall for i in range(m) for j in range(m) for wall in walls_of(i,j)}
    current=(0,0)
    directions=[(-1,0),(0,-1),(1,0),(0,1)]
    seen=set()
    def closed(cell):
        return all(w in walls for w in walls_of(*cell))
    while True:
        state=(current,len(walls))
        if state in seen:
            raise ValueError('the instruction sequences repeat without removing a wall')
        seen.add(state)
        i,j=current
        selected=None
        for index in range(i+j,len(neighbor)):
            di,dj=directions[neighbor[index]]
            nxt=(i+di,j+dj)
            if 0<=nxt[0]<m and 0<=nxt[1]<m and closed(nxt):
                selected=nxt
                break
        if selected is not None:
            shared=(i+selected[0]+1,j+selected[1]+1)
            walls.remove(shared)
            current=selected
            continue
        replacement=None
        for index in range(2*(i+j),len(cells)-1,2):
            candidate=(cells[index],cells[index+1])
            if not closed(candidate) and any(closed(nxt) for nxt,_ in adjacent(m,candidate)):
                replacement=candidate
                break
        if replacement is None:
            return walls
        current=replacement


def corner_count(m, walls):
    result=0
    for i in range(m):
        for j in range(m):
            upper,lower,left,right=[w in walls for w in walls_of(i,j)]
            result += sum([upper,lower,left,right])==2 and not(upper and lower) and not(left and right)
    return result


def longest_passages(m, walls):
    runs=set()
    for i in range(m):
        start=0
        for j in range(m):
            if j==m-1 or (2*i+1,2*j+2) in walls:
                runs.add(tuple((i,k) for k in range(start,j+1)))
                start=j+1
    for j in range(m):
        start=0
        for i in range(m):
            if i==m-1 or (2*i+2,2*j+1) in walls:
                runs.add(tuple((k,j) for k in range(start,i+1)))
                start=i+1
    length=max(map(len,runs))
    return length,sum(len(run)==length for run in runs)


def left_hand_count(m, walls, goal):
    # Clockwise direction order; initially east, so the upper wall is on the left.
    directions=[(-1,0),(0,1),(1,0),(0,-1)]
    current=(0,0); facing=1; visited={current}; states=set()
    while current!=goal:
        state=(current,facing)
        if state in states:
            raise ValueError('the left-hand walk does not reach the goal')
        states.add(state)
        i,j=current
        for direction in[(facing-1)%4,facing,(facing+1)%4,(facing+2)%4]:
            di,dj=directions[direction];nxt=(i+di,j+dj)
            wall=(i+nxt[0]+1,j+nxt[1]+1)
            if 0<=nxt[0]<m and 0<=nxt[1]<m and wall not in walls:
                current=nxt;facing=direction;visited.add(current)
                break
        else:
            raise ValueError('the current cell has no exit')
    return len(visited)


def main(folder):
    sequence=read_numbers(folder/'sequence.txt')
    print('Sequence:',sequence[216],max(sequence))
    for question,walls in[
        (2,make_question2(40,read_numbers(folder/'p.txt'))),
        (3,make_question3(40,read_numbers(folder/'neighbor.txt'),read_numbers(folder/'cell.txt')))
    ]:
        print('Question',question)
        for cell in[(5,25),(20,20),(30,33)]:
            print(cell,tuple(int(w in walls) for w in walls_of(*cell)))
        print('L corners:',corner_count(40,walls))
        if question==3:
            print('Longest passages:',longest_passages(40,walls))
            print('Distinct cells on left-hand walk:',left_hand_count(40,walls,(39,27)))


if __name__=='__main__':
    main(Path(sys.argv[1]) if len(sys.argv)>1 else Path('.'))