Multi-Source BFS Solution for the 2023Q2B Mars Terraforming Challenge

Problem Overview

In a future scenario, Mars can be made habitable on a theoretical level. The planet is represented as a row × column grid where each cell holds one of three values: YES – the cell is already habitable. NO – the cell is convertible but not yet habitable. NA – a dead zone that cannot be traversed or converted.

Initially there may be multiple habitable zones. Each habitable cell can spread to its four orthogonal neighbours (up, down, left, right) each solar day, turning adjacent NO cells into YES. The task is to compute the minimum number of solar days required to convert all NO cells to YES. If some NO cells can never be reached, output -1.

Input Format

The input consists of row × column tokens, each being YES, NO or NA. The grid size satisfies 1 ≤ row, column ≤ 8. Tokens are separated by whitespace and lines end with a newline.

Output Format

Output a single integer: the number of solar days needed for complete conversion, or -1 if conversion is impossible.

Solution Idea

The problem is identical to LeetCode 994 "Rotting Oranges". Because there can be multiple initial habitable cells, a multi‑source BFS is the natural approach:

Collect coordinates of all YES cells and push them into a queue as BFS sources.

Count the total number of NO cells ( num_NO).

Perform level‑order BFS. For each cell popped from the queue, examine its four neighbours. If a neighbour is within bounds, not yet visited, and equals NO, convert it to YES, decrement num_NO, and enqueue it.

Increase the level counter after processing each layer; the level count corresponds to elapsed solar days.

When the queue becomes empty, if num_NO > 0 the conversion is impossible (output -1); otherwise the answer is level - 1 because the initial layer does not represent a day.

Reference Implementation (Python)

from collections import deque

grid = []
# Read input until an empty line
while True:
    line = input()
    if len(line) > 0:
        grid.append(line.split())
    else:
        break

n, m = len(grid), len(grid[0])
num_NO = 0
q = deque()
check = [[False] * m for _ in range(n)]

# Initialize queue with all "YES" cells and count "NO" cells
for i in range(n):
    for j in range(m):
        if grid[i][j] == "YES":
            q.append((i, j))
            check[i][j] = True
        elif grid[i][j] == "NO":
            num_NO += 1

level = 0
while q:
    qSize = len(q)
    level += 1
    for _ in range(qSize):
        x, y = q.popleft()
        for nx, ny in [(x+1, y), (x-1, y), (x, y+1), (x, y-1)]:
            if 0 <= nx < n and 0 <= ny < m and not check[nx][ny] and grid[nx][ny] == "NO":
                q.append((nx, ny))
                check[nx][ny] = True
                num_NO -= 1

# If any "NO" remains, conversion failed
print(-1 if num_NO > 0 else level - 1)

Complexity Analysis

Time complexity: O(M·N), where M and N are the grid dimensions, because each cell is visited at most once.

Space complexity: O(M·N) for the visitation matrix and BFS queue.