How to Find the Highest‑Value Mine Cluster with BFS or DFS

Problem Description

You are given a rectangular map where each cell contains '0' (empty), '1' (silver mine) or '2' (gold mine). A mine cluster is a group of adjacent (up, down, left, right) cells that are either '1' or '2'. Silver mines are worth 1 point, gold mines 2 points. The task is to find the cluster with the greatest total value and output that value.

Input

The map is given as multiple lines of equal length, each line consisting of characters '0', '1', or '2'. The maximum size of the map is 300 × 300.

Output

A single integer representing the maximum cluster value.

Examples

Example 1

22220
00000
00000
01111

Output: 8 Example 2

22220
00020
00010
01111

Output: 15 Example 3

20000
00020
00000
00111

Output:

3

Solution Idea

The problem is essentially the same as the classic "Maximum Area of an Island" (LeetCode 695) but with two different cell values. We can traverse each unvisited mine cell using either Breadth‑First Search (BFS) or Depth‑First Search (DFS), summing the values of visited cells to obtain the cluster value, and keep the maximum across all clusters.

Solution 1: BFS

from collections import deque

# four possible directions
DIRECTIONS = [(0,1), (1,0), (-1,0), (0,-1)]

grid = []
while True:
    row = input()
    if len(row) == 0:
        break
    grid.append(row)

n, m = len(grid), len(grid[0])
ans = 0
check_list = [[0] * m for _ in range(n)]

for i in range(n):
    for j in range(m):
        if grid[i][j] != "0" and check_list[i][j] == 0:
            q = deque()
            q.append([i, j])
            check_list[i][j] = 1
            cur_value = 0
            while q:
                x, y = q.popleft()
                cur_value += int(grid[x][y])
                for dx, dy in DIRECTIONS:
                    nxt_x, nxt_y = x + dx, y + dy
                    if 0 <= nxt_x < n and 0 <= nxt_y < m:
                        if grid[nxt_x][nxt_y] != "0" and check_list[nxt_x][nxt_y] == 0:
                            q.append([nxt_x, nxt_y])
                            check_list[nxt_x][nxt_y] = 1
            ans = max(cur_value, ans)

print(ans)

Solution 2: DFS

DIRECTIONS = [(0,1), (1,0), (-1,0), (0,-1)]

grid = []
while True:
    row = input()
    if len(row) == 0:
        break
    grid.append(row)

n, m = len(grid), len(grid[0])
ans = 0
check_list = [[0] * m for _ in range(n)]

def dfs(x, y):
    global cur_value
    check_list[x][y] = 1
    cur_value += int(grid[x][y])
    for dx, dy in DIRECTIONS:
        nxt_x, nxt_y = x + dx, y + dy
        if 0 <= nxt_x < n and 0 <= nxt_y < m:
            if grid[nxt_x][nxt_y] != "0" and check_list[nxt_x][nxt_y] == 0:
                dfs(nxt_x, nxt_y)

for i in range(n):
    for j in range(m):
        if grid[i][j] != "0" and check_list[i][j] == 0:
            cur_value = 0
            dfs(i, j)
            ans = max(ans, cur_value)

print(ans)

Complexity Analysis

Both BFS and DFS visit each cell at most once, giving a time complexity of O(M × N) where M and N are the grid dimensions. The auxiliary space used for the visited matrix and the queue/recursion stack is also O(M × N) in the worst case.