Prerequisites

• Basic understanding of dynamic programming
• Proficiency with binary bitwise operations

Approach

This is a classic bitmask dynamic programming problem. Define dp[i][curr_idx] as the number of valid placement schemes after processing the first i rows, where the curr_idx-th precomputed valid mask represents the placement state of the i-th row.

Each row's placement state can be encoded as a binary number: a 1 bit at position j means a fish is placed at that column, while 0 means the position is empty. For example, the binary mask 10100 for a 5-column row indicates fish are placed at the 1st and 3rd columns.

First, we perprocess all valid single-row placement masks. Per problem constraints, no two fish can be adjacent in the same row, meaning no two 1 bits can be adjacent in the mask. We can filter invalid masks with a simple bitwise check: for any candidate mask mask, if ((mask << 1) | (mask >> 1)) & mask is non-zero, adjacent 1 bits exist, so we discard the mask.

We also preprocess a blocked mask for each row, to account for cells that cannot hold fish. If a cell at column j in row i is blocked, we set the j-th bit in the row's blocked mask to 1. Any placement mask that has a 1 bit overlapping with a set bit in the row's blocked mask is invalid and will be skippped.

Next, we handle conflicts between adjacent rows. If the previous row's mask is prev_mask and the current row's mask is curr_mask, a non-zero result from prev_mask & curr_mask means fish are placed in the same column of adjacent rows, which violates the problem constraints, so this transition is discarded.

The state transittion equation is: dp[i][curr_idx] = (dp[i][curr_idx] + dp[i-1][prev_idx]) % MOD where curr_idx is a valid mask for the current row, and prev_idx is a valid mask for the previous row with no overlap with curr_idx.

The base case is initialized as dp[0][0] = 1, representing one valid way to have an empty grid with zero rows processed.

The final answer is the sum of all dp[n][curr_idx] for all valid current masks, minus 1 to exclude the case where no fish are placed at all (as required by the problem statement).

Time Complexity

A naive analysis gives a time complexity of O(n * 4^m), as we iterate over rows, and all possible masks for current and previous rows. However, since most masks are invalid (contain adjacent 1 bits), the actual number of valid masks is far smaller than 2^m, so the actual runtime is much faster than the worst case.

C++ Implementation

#include <iostream>
using namespace std;

const int MOD = 1000000007;
int rows, cols, total_ans;
int grid[505][505];
int row_block_mask[505];
int valid_masks[1050];
int mask_count = 0;
long long dp[505][1050];

int main(){
    cin >> rows >> cols;
    for (int i = 1; i <= rows; i++){
        for (int j = 1; j <= cols; j++){
            cin >> grid[i][j];
        }
    }
    
    // Precompute blocked positions for each row
    for (int i = 1; i <= rows; i++){
        row_block_mask[i] = 0;
        for (int j = 1; j <= cols; j++){
            row_block_mask[i] = (row_block_mask[i] << 1) + (grid[i][j] == 0 ? 1 : 0);
        }
    }
    
    // Precompute all single-row valid masks
    for (int mask = 0; mask < (1 << cols); mask++){
        if (((mask << 1) | (mask >> 1)) & mask) continue;
        valid_masks[++mask_count] = mask;
    }
    
    dp[0][1] = 1; // Base case: empty state
    
    // Process each row
    for (int i = 1; i <= rows; i++){
        // Enumerate all possible masks for current row
        for (int curr = 1; curr <= mask_count; curr++){
            int curr_mask = valid_masks[curr];
            // Skip if current mask has fish on blocked cells
            if (curr_mask & row_block_mask[i]) continue;
            // Enumerate all possible masks from previous row
            for (int prev = 1; prev <= mask_count; prev++){
                int prev_mask = valid_masks[prev];
                // Check previous row mask against its blocked cells
                if (prev_mask & row_block_mask[i-1]) continue;
                // No overlapping fish between adjacent rows
                if (curr_mask & prev_mask) continue;
                dp[i][curr] = (dp[i][curr] + dp[i-1][prev]) % MOD;
            }
        }
    }
    
    // Calculate final answer
    total_ans = 0;
    for (int i = 1; i <= mask_count; i++){
        total_ans = (total_ans + dp[rows][i]) % MOD;
    }
    
    cout << (total_ans - 1 + MOD) % MOD << endl;
    return 0;
}

Python Implementation

This implementation passes all test cases for the problem:

MOD = 10**9 + 7

def main():
    rows, cols = map(int, input().split())
    grid = [[0]*(cols + 1)]
    for _ in range(rows):
        row = [0] + list(map(int, input().split()))
        grid.append(row)
    
    # Precompute blocked mask for each row
    row_block = [0]*(rows + 1)
    for i in range(1, rows + 1):
        for j in range(1, cols + 1):
            row_block[i] = (row_block[i] << 1) + (1 - grid[i][j])
    
    # Precompute all valid single-row masks
    valid_masks = []
    for mask in range(1 << cols):
        if not (((mask << 1) | (mask >> 1)) & mask):
            valid_masks.append(mask)
    mask_count = len(valid_masks)
    
    # DP table
    dp = [[0]*mask_count for _ in range(rows + 1)]
    dp[0][0] = 1 # empty base case
    
    for i in range(1, rows + 1):
        for curr in range(mask_count):
            curr_mask = valid_masks[curr]
            if curr_mask & row_block[i]:
                continue
            for prev in range(mask_count):
                prev_mask = valid_masks[prev]
                if prev_mask & row_block[i-1]:
                    continue
                if curr_mask & prev_mask:
                    continue
                dp[i][curr] = (dp[i][curr] + dp[i-1][prev]) % MOD
    
    ans = sum(dp[rows]) % MOD
    # Subtract empty arrangement
    print((ans - 1) % MOD)

if __name__ == "__main__":
    main()

Brute Force DFS for Testing

This brute force approach can be used for correctness testing on small test cases:

#include <iostream>
using namespace std;

const int MOD = 1000000007;
int n, m, ans;
int grid[15][15];
int dirs[4][2] = {{0,1}, {1,0}, {0,-1}, {-1,0}};

void dfs(int x, int y){
    if (x > n) {
        ans = (ans + 1) % MOD;
        return;
    }
    if (y > m) {
        dfs(x + 1, 1);
        return;
    }
    // Can't place here, move on
    if (grid[x][y] == 0) {
        dfs(x, y + 1);
        return;
    }
    // Option 1: don't place fish here
    dfs(x, y + 1);

    // Option 2: place fish here, check adjacency
    bool can_place = true;
    for (int i = 0; i < 4; i++) {
        int nx = x + dirs[i][0];
        int ny = y + dirs[i][1];
        if (nx < 1 || ny < 1 || nx > n || ny > m) continue;
        // Already placed fish adjacent
        if (grid[nx][ny] == 2) {
            can_place = false;
            break;
        }
    }
    if (can_place) {
        grid[x][y] = 2;
        dfs(x, y + 1);
        grid[x][y] = 1; // backtrack
    }
    return;
}

int main(){
    cin >> n >> m;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            cin >> grid[i][j];
        }
    }
    dfs(1, 1);
    cout << (ans - 1 + MOD) % MOD << endl;
    return 0;
}