Constraints

• 1 <= m, n <= 200
• 0 <= len(bombs) <= m * n
• Bomb coordinates are distinct and within bounds
• 0 <= len(operations) <= 10^4
• Click coordinates may be out of bounds; such clicks are ignored
• Coordinates are 0-indexed

Examples

Solution

def solution(m, n, bombs, operations):
    from collections import deque

    bomb_set = {tuple(cell) for cell in bombs}
    counts = [[0] * n for _ in range(m)]
    directions = [(-1, -1), (-1, 0), (-1, 1),
                  (0, -1),           (0, 1),
                  (1, -1),  (1, 0),  (1, 1)]

    for r, c in bomb_set:
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if 0 <= nr < m and 0 <= nc < n and (nr, nc) not in bomb_set:
                counts[nr][nc] += 1

    revealed = [[False] * n for _ in range(m)]
    game_over = False
    exploded = None

    def reveal_from(sr, sc):
        if revealed[sr][sc]:
            return
        if counts[sr][sc] != 0:
            revealed[sr][sc] = True
            return

        queue = deque([(sr, sc)])
        revealed[sr][sc] = True

        while queue:
            r, c = queue.popleft()
            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                if not (0 <= nr < m and 0 <= nc < n):
                    continue
                if revealed[nr][nc] or (nr, nc) in bomb_set:
                    continue
                revealed[nr][nc] = True
                if counts[nr][nc] == 0:
                    queue.append((nr, nc))

    def print_board():
        lines = []
        for r in range(m):
            row = []
            for c in range(n):
                if exploded == (r, c):
                    row.append('X')
                elif revealed[r][c]:
                    row.append(str(counts[r][c]))
                else:
                    row.append('#')
            lines.append(' '.join(row))
        return '\n'.join(lines)

    outputs = []
    for op in operations:
        parts = op.split()
        if not parts:
            continue

        if parts[0] == 'click':
            if game_over or len(parts) != 3:
                continue
            r, c = int(parts[1]), int(parts[2])
            if not (0 <= r < m and 0 <= c < n):
                continue
            if (r, c) in bomb_set:
                game_over = True
                exploded = (r, c)
            else:
                reveal_from(r, c)
        elif parts[0] == 'print':
            outputs.append(print_board())

    return outputs

Time complexity: O(m*n + P*m*n + R), where P is the number of `print` operations and R is the total number of cells ever revealed by clicks (R <= m*n).. Space complexity: O(m*n).

Hints

1. Precompute the adjacent bomb count for every non-bomb cell once at the start.
2. For revealing a zero cell, use BFS or DFS over 8 directions, and reveal bordering numbered cells as you expand.

Constraints

• 1 <= m, n <= 10^9
• 0 <= len(bombs) <= 200
• 1 <= len(clicks) <= 10^5
• Bomb coordinates are distinct and within bounds
• Click coordinates are within bounds
• Coordinates are 0-indexed

Examples

Solution

def solution(m, n, bombs, clicks):
    from bisect import bisect_right
    from collections import deque

    bomb_set = {tuple(cell) for cell in bombs}
    row_starts = {0, m}
    col_starts = {0, n}

    for r, c in bomb_set:
        for x in (r - 1, r, r + 1):
            if 0 <= x < m:
                row_starts.add(x)
                row_starts.add(x + 1)
        for y in (c - 1, c, c + 1):
            if 0 <= y < n:
                col_starts.add(y)
                col_starts.add(y + 1)

    rows = sorted(row_starts)
    cols = sorted(col_starts)
    R = len(rows) - 1
    C = len(cols) - 1
    row_len = [rows[i + 1] - rows[i] for i in range(R)]
    col_len = [cols[j + 1] - cols[j] for j in range(C)]

    status = [[0] * C for _ in range(R)]
    # 0 = zero region, 1 = numbered cell, 2 = bomb

    for i in range(R):
        if row_len[i] != 1:
            continue
        r0 = rows[i]
        for j in range(C):
            if col_len[j] != 1:
                continue
            c0 = cols[j]
            if (r0, c0) in bomb_set:
                status[i][j] = 2
                continue

            numbered = False
            for dr in (-1, 0, 1):
                for dc in (-1, 0, 1):
                    if dr == 0 and dc == 0:
                        continue
                    if (r0 + dr, c0 + dc) in bomb_set:
                        numbered = True
                        break
                if numbered:
                    break
            if numbered:
                status[i][j] = 1

    comp = [[-1] * C for _ in range(R)]
    reveal_size = []
    dirs = [(-1, -1), (-1, 0), (-1, 1),
            (0, -1),           (0, 1),
            (1, -1),  (1, 0),  (1, 1)]

    for i in range(R):
        for j in range(C):
            if status[i][j] != 0 or comp[i][j] != -1:
                continue

            cid = len(reveal_size)
            queue = deque([(i, j)])
            comp[i][j] = cid
            zero_area = 0
            border = set()

            while queue:
                x, y = queue.popleft()
                zero_area += row_len[x] * col_len[y]

                for dx, dy in dirs:
                    nx, ny = x + dx, y + dy
                    if not (0 <= nx < R and 0 <= ny < C):
                        continue
                    if status[nx][ny] == 0:
                        if comp[nx][ny] == -1:
                            comp[nx][ny] = cid
                            queue.append((nx, ny))
                    elif status[nx][ny] == 1:
                        border.add((nx, ny))

            reveal_size.append(zero_area + len(border))

    answers = []
    for r, c in clicks:
        i = bisect_right(rows, r) - 1
        j = bisect_right(cols, c) - 1
        cell_type = status[i][j]
        if cell_type == 2:
            answers.append(-1)
        elif cell_type == 1:
            answers.append(1)
        else:
            answers.append(reveal_size[comp[i][j]])

    return answers

Time complexity: O(S^2 + q log S), where q = len(clicks) and S = O(k) is the number of compressed row/column segments derived from k bombs.. Space complexity: O(S^2).

Hints

1. Only rows and columns within distance 1 of some bomb can contain non-zero cells. Everything else is guaranteed to be zero.
2. Coordinate-compress the interesting rows and columns, build zero-components on the compressed grid, and precompute each component's reveal size.