如何在Python 2.x中统计数组中独立连通区域的数量

Hey there! Let's fix that connected components counting issue you're having. The problem with just counting unique strings is that it doesn't distinguish between separate "islands" of the same value—like those two distinct 64733 regions in your example grid.

For Python 2.x, we can use a Breadth-First Search (BFS) approach to traverse each connected region, mark cells as visited once we process them, and count each unique traversal as a separate region. Here's how to implement it step by step:

Step 1: Preprocess the 3D Input (if needed) #

Your input is a 3D array where each grid cell is split into individual characters (e.g., ['6','4','7','3','3'] instead of '64733'). First, we'll convert this into a 2D array of full strings for easier comparison:

from collections import deque

def preprocess_3d_grid(input_3d):
    # Convert 3D grid to 2D grid of concatenated strings
    return [[''.join(cell) for cell in row] for row in input_3d]

Step 2: Count Connected Components #

Next, we'll write the core function to count regions. We'll use a visited matrix to track which cells we've already processed, and BFS to explore all adjacent cells of the same value:

def count_connected_regions(grid):
    if not grid or not grid[0]:
        return 0
    
    rows = len(grid)
    cols = len(grid[0])
    visited = [[False for _ in xrange(cols)] for _ in xrange(rows)]
    region_count = 0
    # Define up, down, left, right directions (no diagonals)
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    
    for i in xrange(rows):
        for j in xrange(cols):
            if not visited[i][j]:
                # Found a new region
                region_count += 1
                current_value = grid[i][j]
                # Initialize BFS queue
                queue = deque()
                queue.append((i, j))
                visited[i][j] = True
                
                while queue:
                    x, y = queue.popleft()
                    # Check all four directions
                    for dx, dy in directions:
                        nx = x + dx
                        ny = y + dy
                        # Check if the neighbor is within bounds, unvisited, and same value
                        if 0 <= nx < rows and 0 <= ny < cols:
                            if not visited[nx][ny] and grid[nx][ny] == current_value:
                                visited[nx][ny] = True
                                queue.append((nx, ny))
    return region_count

Step 3: Put It All Together #

To use these functions with your input:

# Example input snippet (replace with your full 3D array)
input_3d = [
    [['6', '4', '7', '3', '3'], ['2', '0', '9', '9', '6'], ['9', '2', '3', '6', '0']],
    [['6', '4', '7', '3', '3'], ['9', '2', '3', '6', '0'], ['9', '2', '3', '6', '0']],
    [['6', '4', '7', '3', '3'], ['9', '2', '3', '6', '0'], ['2', '9', '1', '3', '6']]
]

# Preprocess and count
grid_2d = preprocess_3d_grid(input_3d)
total_regions = count_connected_regions(grid_2d)
print("Total connected regions:", total_regions)

Key Notes: #

• BFS vs DFS: We used BFS here because it's efficient for grid traversal and avoids recursion depth issues (which can happen with DFS for large grids). If you prefer DFS, you could replace the queue with a stack (using append() and pop() instead of popleft()).
• Visited Matrix: This ensures we don't count the same cell multiple times, which is crucial for accurate region counting.
• Direction Handling: We only check up, down, left, right—no diagonals, which matches your region definition.

Testing this with your example grid, it will correctly count the two separate 64733 regions as distinct, along with all other unique connected areas of the same string.

内容的提问来源于stack exchange，提问作者Orgenplop