Overview

This is a problem where you simulate the result of pressing a given stamp multiple times at specified positions, and determine what the sheet of paper looks like.

Analysis

In this problem, we can find the answer by simulating each of the \(N\) stamp operations one by one.

The key points are as follows:

• The stamp always has the same shape, and whether a cell on the sheet gets marked depends on whether the corresponding stamp cell is # or ..
• Since the top-left corner of the stamp is aligned to \((r_i, c_i)\), we can calculate which position on the sheet each stamp cell corresponds to.
• However, the stamp may extend beyond the boundaries of the sheet, so we need to prevent out-of-bounds access.
• Additionally, once a cell becomes #, it remains # even if stamped again, so we can simply overwrite it.

A straightforward approach is to examine all cells of the stamp for each operation and apply them to the sheet. This is sufficiently fast because the stamp size is at most \(100 \times 100\), and the number of operations is at most 1000, resulting in at most \(100 \times 100 \times 1000 = 10^7\) computations, which fits within the time limit.

Algorithm

1. Read the input. In particular, since the coordinates are given in 1-indexed form, convert them to 0-indexed for internal processing.
2. Initialize a two-dimensional array paper representing the sheet with ..
3. For each stamp press, perform the following:
   • For each # cell \((dr, dc)\) of the stamp, calculate which position \((r_{\text{paper}}, c_{\text{paper}})\) on the sheet it corresponds to: $\( r_{\text{paper}} = r_{\text{top}} + dr,\quad c_{\text{paper}} = c_{\text{left}} + dc \)$
   • If that position is within the bounds of the sheet (\(0 \leq r_{\text{paper}} < H\) and \(0 \leq c_{\text{paper}} < W\)), set that cell to #.
4. Output the final state of the sheet.

Complexity

• Time complexity: \(O(N \cdot R \cdot C)\)
• Space complexity: \(O(H \cdot W + R \cdot C)\)

※ Where the sheet size is \(H \times W\), the stamp size is \(R \times C\), and the number of stamp presses is \(N\).

Implementation Notes

• Since coordinates are given in 1-indexed form in the input, convert them to 0-indexed internally.

• By processing only the # cells of the stamp, the simulation can be done efficiently.

• To prevent out-of-bounds access, verify that \(0 \leq r < H\) and \(0 \leq c < W\) before updating.

  Source Code

H, W = map(int, input().split())
R, C = map(int, input().split())
stamp = [input() for _ in range(R)]
N = int(input())
stamps = [tuple(map(int, input().split())) for _ in range(N)]

# 1-indexed -> 0-indexed
stamps = [(r - 1, c - 1) for r, c in stamps]

# 台紙の初期化
paper = [['.' for _ in range(W)] for _ in range(H)]

# スタンプを押す処理
for r_top, c_left in stamps:
    for dr in range(R):
        for dc in range(C):
            if stamp[dr][dc] == '#':
                r_paper = r_top + dr
                c_paper = c_left + dc
                if 0 <= r_paper < H and 0 <= c_paper < W:
                    paper[r_paper][c_paper] = '#'

# 出力
for row in paper:
    print(''.join(row))

This editorial was generated by qwen3-coder-480b.