How to Minimize Clicks in the “Happy Elimination” Grid Puzzle Using BFS/DFS

Problem Description

Given an N × M binary matrix (values are 0 or 1), clicking a cell that contains 1 flips it to 0 and also flips any adjacent 1 s in the eight possible directions (up, down, left, right, and the four diagonals). The goal is to make the entire matrix consist of zeros with the fewest clicks.

Input & Output

The first line contains two integers N and M (1 ≤ N, M ≤ 100). The next N lines each contain M numbers (0 or 1) describing the initial matrix. Output a single integer – the minimal number of clicks required.

Example Explanation

For the 3 × 3 matrix

1 0 1
0 1 0
1 0 1

all four corner 1 s are adjacent to the central 1 in the eight‑direction sense, so a single click on the center turns every 1 to 0. Hence the answer is 1.

Solution Insight

The problem is essentially identical to LeetCode 200 (Number of Islands) except that connectivity is defined over eight directions instead of four. Each click eliminates an entire connected component of 1 s, so the minimum number of clicks equals the number of such components.

Direction Array

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

Solution 1: BFS

# 题目：2023Q1A-开心消消乐
# 分值：100
# 作者：闭着眼睛学数理化
# 算法：BFS

from collections import deque

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

n, m = map(int, input().split())
grid = []
for _ in range(n):
    grid.append(input().split())

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

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

print(ans)

Solution 2: DFS

# 题目：2023Q1A-开心消消乐
# 分值：100
# 作者：闭着眼睛学数理化
# 算法：DFS

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

n, m = map(int, input().split())
grid = []
for _ in range(n):
    grid.append(input().split())

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

def dfs(x, y):
    check_list[x][y] = 1
    for dx, dy in DIRECTIONS:
        nx, ny = x + dx, y + dy
        if 0 <= nx < n and 0 <= ny < m:
            if grid[nx][ny] == "1" and check_list[nx][ny] == 0:
                dfs(nx, ny)

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

print(ans)

Complexity Analysis

Time complexity: O(N × M) – each cell is visited at most once.

Space complexity: O(N × M) for the visited matrix and the BFS/DFS stack or queue.