Overview

This is a problem where you enlarge the original design by a factor of \(K\) and output a mosaic art with the specified character replacements.

Analysis

The original design is given as an \(H \times W\) grid. Since we enlarge it by a factor of \(K\) both vertically and horizontally, the final size becomes \(HK \times WK\).

A naive approach of “replacing each cell with a \(K \times K\) block” through simulation could result in excessive computation. For example, if we loop \(K \times K\) times for each cell, we would need \(H \times W \times K \times K\) total operations, which in the worst case would be \(100 \times 100 \times 50 \times 50 = 25000000\) operations, potentially taking too long.

However, processing row by row is actually efficient. That is, we can expand one original row to create a single enlarged row, and then simply repeat it \(K\) times. This way, for each row we only need to construct a string of length \(W \times K\) once and output it \(K\) times, making the process both fast and simple.

For example, given the following input:

2 3 2
A B
#.#
.#.

The first row #.# is expanded to AABB (note: # becomes A repeated \(K\) times, . becomes B repeated \(K\) times), which is output 2 times. Similarly, the second row .#. is expanded to BAAB, which is also output 2 times.

By processing row by row like this, we reduce unnecessary loops and keep the code simple.

Algorithm

1. For each row, examine the original string character by character: if it is #, concatenate \(K\) copies of \(c_1\); if it is ., concatenate \(K\) copies of \(c_2\), forming a new row.
2. Output that row \(K\) times.
3. Repeat this for all rows.

Complexity

• Time complexity: \(O(HK \cdot WK) = O(HWK^2)\)
• Space complexity: \(O(WK)\) (storing one row’s string)

*The time complexity is proportional to the total number of characters output. Since this is unavoidable, it is optimal.

Implementation Notes

• The key point is to convert each row only once and output it \(K\) times.

• In Python, string concatenation is easy using + and *.

• Pay attention to how you read the input (e.g., using list comprehensions).

  Source Code

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

for i in range(H):
    # 拡大前の1行をK倍してK行分作る
    row = ""
    for j in range(W):
        if S[i][j] == '#':
            row += c1 * K
        else:
            row += c2 * K
    # K回繰り返して出力
    for _ in range(K):
        print(row)

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