Overview

This is a problem where you need to output the state of a card after punching holes at \(K\) specified locations on an \(N \times M\) grid.

Analysis

This problem is a simulation problem using a two-dimensional array.

Key Observations

1. Initial state: All cells are # (no hole)
2. Operation: Change the cell at the specified coordinates to . (hole present)
3. Coordinate handling: The problem statement uses 1-indexed (starting from 1), but programs often use 0-indexed (starting from 0)

Why This Problem Can Be Solved Simply

• Each hole-punching operation is independent, and the order doesn’t matter
• The same position is never specified more than once (from the constraints)
• Since we’re just modifying specific positions in the array, each operation completes in \(O(1)\)

A straightforward approach is fast enough, so no special techniques are needed.

Algorithm

1. Create an \(N \times M\) two-dimensional array and initialize all elements with #
2. In a loop of \(K\) iterations, change the position at the specified coordinates \((R_i, C_i)\) to .
   • At this point, convert the coordinates to 0-indexed (\(R_i - 1\), \(C_i - 1\))
3. Output the two-dimensional array row by row

Concrete Example

Consider the following input:

3 4 2
1 2
2 3

Step 1: Initial state (\(3 \times 4\) grid)

####
####
####

Step 2: Punch a hole at \((1, 2)\) → In the array: [0][1]

#.##
####
####

Step 3: Punch a hole at \((2, 3)\) → In the array: [1][2]

#.##
##.#
####

Complexity

• Time complexity: \(O(N \times M + K)\)
  • Array initialization: \(O(N \times M)\)
  • Punching \(K\) holes: \(O(K)\)
  • Output: \(O(N \times M)\)
• Space complexity: \(O(N \times M)\)
  • For storing the \(N \times M\) two-dimensional array

Implementation Notes

1. Index conversion for coordinates: The problem statement is 1-indexed, but Python lists are 0-indexed, so convert using R - 1 and C - 1
2. List initialization: Using list comprehension like [['#'] * M for _ in range(N)] makes the code concise
   • Caution: Writing [['#'] * M] * N will duplicate references to the same list, causing bugs
3. Joining for output: Each row is a list of characters, so use ''.join(row) to concatenate into a string for output

Source Code

# Receive input
N, M, K = map(int, input().split())

# Create a card with all cells being '#'
card = [['#'] * M for _ in range(N)]

# Punch holes at K locations
for _ in range(K):
    R, C = map(int, input().split())
    card[R - 1][C - 1] = '.'

# Output the result
for row in card:
    print(''.join(row))

---

This editorial was generated by claude4.5opus.