Overview

This is a problem where you enlarge the original design by a factor of \(K\) both vertically and horizontally, replace the specified characters, and output the resulting mosaic art.

Analysis

In this problem, we need to enlarge the original \(H \times W\) grid by a factor of \(K\). A naive approach of directly constructing the enlarged \(HK \times WK\) grid would require processing each cell individually, resulting in a time complexity of \(O(H \cdot W \cdot K^2)\). However, given the constraints of at most \(H=100, W=100, K=50\), this would require \(100 \times 100 \times 50^2 = 25,000,000\) operations, which could be too slow for interpreter languages like Python.

However, by leveraging the repeating pattern of each row and column, we can efficiently construct the enlarged grid. Specifically, we repeat each cell of the original grid \(K\) times horizontally, and then repeat each row \(K\) times vertically, to efficiently generate the enlarged grid.

Algorithm

1. For each row of the original grid, perform character conversion (# → \(c_1\), . → \(c_2\)) on each cell, then repeat each character \(K\) times to generate the horizontally enlarged row.
2. Repeat each generated row \(K\) times to achieve vertical enlargement, and output it.

With this approach, we only perform horizontal enlargement once per original row and then output it \(K\) times, significantly reducing the computational cost.

Complexity

• Time complexity: \(O(H \cdot W \cdot K)\)
  • We process each cell of the original grid (\(H \cdot W\) times), and for each cell, perform a string repetition operation \(K\) times.
• Space complexity: \(O(H \cdot W \cdot K)\)
  • To hold one row of the enlarged grid (at most \(W \cdot K\) characters).

Implementation Notes

• Use string multiplication (char * K) to efficiently perform horizontal enlargement.

• After horizontally enlarging each row, output that row \(K\) times to achieve vertical enlargement.

• For memory efficiency, instead of holding the entire enlarged grid at once, generate and output it one row at a time.

  Source Code

H, W, K = map(int, input().split())
c1, c2 = input().split()
grid = [input() for _ in range(H)]

for i in range(H):
    expanded_row = []
    for j in range(W):
        char = c1 if grid[i][j] == '#' else c2
        expanded_row.append(char * K)
    expanded_line = ''.join(expanded_row)
    for _ in range(K):
        print(expanded_line)

This editorial was generated by deepseekv3.