Overview

This problem asks us to output the final state of an H-row by W-column sheet after pressing an R-row by C-column stamp N times. The stamp may partially extend outside the sheet, and any such out-of-bounds portions are ignored.

Analysis

The key observations for solving this problem are as follows: - The stamp placement positions can be negative or outside the range of the sheet - We need to check whether each cell of the stamp falls within the sheet - For each stamp operation, we update the corresponding cells on the sheet to “#” where the stamp has “#” - Cells that are already “#” remain as they are (overlapping stamps cause no issues)

A straightforward approach is to scan the entire stamp for each stamp operation and update the corresponding positions on the sheet. Given the constraints (H, W ≤ 1000, R, C ≤ 100, N ≤ 1000), the worst-case computation is O(N×R×C) = 1000×100×100 = 10^7 operations, which is well within the time limit.

Algorithm

1. Initialize the H-row by W-column sheet with all “.”
2. Process each of the N stamp operations in order:
   • For each operation, receive the top-left position (r_i, c_i) of the stamp
   • For each cell (dr, dc) of the stamp:
     • The corresponding position on the sheet: row = r_i - 1 + dr, column = c_i - 1 + dc
     • If this position is within the sheet bounds (0 ≤ row < H, 0 ≤ column < W) and the corresponding stamp cell is “#”, update the sheet cell to “#”
3. Output the final state of the sheet

Complexity

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

Implementation Notes

• Stamp positions are given in 1-indexed format, so they need to be converted to 0-indexed (r_i - 1, c_i - 1)

• Use nested loops to scan all cells of the stamp, but do not forget the bounds check

• Efficiency is improved by only processing stamp cells that are “#”

• Overwriting a cell that is already “#” with “#” again causes no issues (the result is the same)

  Source Code

def main():
    import sys
    data = sys.stdin.read().splitlines()
    idx = 0
    H, W = map(int, data[idx].split())
    idx += 1
    R, C = map(int, data[idx].split())
    idx += 1
    stamp = []
    for _ in range(R):
        stamp.append(data[idx].strip())
        idx += 1
    N = int(data[idx])
    idx += 1
    operations = []
    for _ in range(N):
        r, c = map(int, data[idx].split())
        idx += 1
        operations.append((r, c))
    
    grid = [['.'] * W for _ in range(H)]
    
    for op in operations:
        r0, c0 = op
        for dr in range(R):
            r_pos = r0 - 1 + dr
            if r_pos < 0 or r_pos >= H:
                continue
            for dc in range(C):
                c_pos = c0 - 1 + dc
                if c_pos < 0 or c_pos >= W:
                    continue
                if stamp[dr][dc] == '#':
                    grid[r_pos][c_pos] = '#'
                    
    for i in range(H):
        print(''.join(grid[i]))

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.