n×m布尔数组A中可容纳p×q布尔数组B的最大数量问询

Got it, let's tackle this problem properly. First, let's clarify the problem statement to avoid any ambiguity, then walk through solutions ranging from simple quick wins to optimal approaches.

Problem Recap #

We have two randomly initialized boolean arrays:

• Map array A (size n×m): A[x][y] = true means this spot is an obstacle; false means it's a free, placeable area.
• Pattern array B (size p×q, with p≤n, q≤m): B[i][j] = true means placing the pattern here requires the corresponding map spot to be free (i.e., A[k+i][l+j] must be false). B[i][j] = false spots don't impose any restrictions on the map.

Our goal is to find the maximum number of non-overlapping instances of B we can place on A, following the rule: a placement at top-left coordinate (k,l) is valid if ¬(A[k+i][l+j] ∧ B[i][j]) holds for all 0≤i<p, 0≤j<q.

Step 1: Preprocess to Find All Valid Placement Spots #

First, we need to identify every (k,l) where we can place B. This is straightforward—we just check each candidate position against the pattern, with a small optimization to skip irrelevant spots in B:

def get_valid_placements(A, B, n, m, p, q):
    # Precompute only the (i,j) in B that are true (these are the only spots we need to check)
    required_free_spots = [(i,j) for i in range(p) for j in range(q) if B[i][j]]
    
    valid_placements = []
    for k in range(n - p + 1):
        for l in range(m - q + 1):
            can_place = True
            for (i,j) in required_free_spots:
                if A[k+i][l+j]:
                    can_place = False
                    break
            if can_place:
                # Store placement with its bottom-right coordinates for easier overlap checks
                valid_placements.append( (k, l, k+p-1, l+q-1) )
    return valid_placements

Step 2: Calculate Maximum Non-Overlapping Placements #

This is the core challenge—selecting the largest subset of valid spots where no two placements overlap. Here are your go-to options:

Option 1: Greedy Algorithm (Fast, Simple, But Not Always Optimal) #

If you need a quick solution and don't mind potentially missing the absolute maximum, a greedy approach works well. We pick placements in top-to-bottom, left-to-right order, mark their area as occupied, and keep going:

def greedy_max_count(valid_placements, n, m):
    occupied = [[False]*m for _ in range(n)]
    count = 0
    
    for (k, l, br_k, br_l) in valid_placements:
        # Check if this placement overlaps with any already occupied area
        has_overlap = False
        for i in range(k, br_k+1):
            for j in range(l, br_l+1):
                if occupied[i][j]:
                    has_overlap = True
                    break
            if has_overlap:
                break
        if not has_overlap:
            count +=1
            # Mark the entire placement area as occupied
            for i in range(k, br_k+1):
                for j in range(l, br_l+1):
                    occupied[i][j] = True
    return count

Pros: Super easy to implement, fast for small to medium maps.
Cons: Doesn't guarantee the global maximum—sometimes choosing a later placement allows more total placements.

Option 2: Dynamic Programming (Optimal, For Small-Medium Maps) #

If you need the optimal solution and your map isn't huge (e.g., n,m ≤ 50), use dynamic programming. We sort valid placements by their bottom-right corner, then track the maximum count up to each placement:

def dp_max_count(valid_placements):
    # Sort placements by their bottom-right y-coordinate, then x-coordinate
    valid_placements.sort(key=lambda x: (x[3], x[2]))
    total_placements = len(valid_placements)
    dp = [1]*total_placements  # dp[i] = max count including the i-th placement
    
    for i in range(total_placements):
        curr_k, curr_l, curr_brk, curr_brl = valid_placements[i]
        # Find the last placement that doesn't overlap with the current one
        for j in range(i-1, -1, -1):
            prev_k, prev_l, prev_brk, prev_brl = valid_placements[j]
            if prev_brk < curr_k and prev_brl < curr_l:
                dp[i] = max(dp[i], dp[j]+1)
                break  # No need to check earlier placements since we sorted them
    
    return max(dp) if dp else 0

Pros: Guarantees the optimal count, efficient if the number of valid placements isn't massive.
Cons: Performance drops if there are thousands of valid spots.

Option 3: Max Flow/Bipartite Matching (Optimal, For Larger Scales) #

For larger maps with lots of valid placements, model this as a maximum independent set problem (which translates to a max flow problem):

1. Treat each valid placement as a node in a graph.
2. Add an edge between two nodes if their placements overlap (they can't be chosen together).
3. The maximum independent set (largest subset of non-overlapping nodes) equals total_nodes - minimum_vertex_cover, and by Konig's theorem, the minimum vertex cover equals the maximum matching in a bipartite graph.

You can implement this using standard max flow algorithms like Dinic's algorithm. This is the most scalable optimal approach for large datasets.

Optimizations for Randomly Initialized Arrays #

Since A and B are random, we can leverage their properties:

• If B has a high density of true values, valid placements will be rare—greedy or DP will work perfectly.
• If B has few true values, valid placements will be numerous—sort-based DP or max flow is your best bet.
• For very large maps, split the map into smaller chunks, compute the max count for each chunk, and sum them (this is an approximation but works well for random obstacle distributions).

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