In an N×M (N<100, M<10) grid, we need to place cannons on plains (P) while avoiding mountains (H). Cannons attack in a cross pattern: 2 cells left and right horizontally, and 2 cells up and down vertically. Cannons cannot attack each other. The goal is to maximize the number of cannons placed.

Example input:

5 4
PHPP
PPHH
PPPP
PHPP
PHHP

Approach

Since each cell has two possible states (place a cannon or not), exhaustive search would be infeasible. We use state compression dynamic programming instead.

We compress each row's state into a bitmask. The DP state dp[i][j][k] represents the maximum number of cannons for the first i rows, where row i has state j and row i-1 has state k.

The transition considers:

1. Valid horizontal placements (no adjacent cannons)
2. Compatibility with the map (cannot place on mountains)
3. No conflicts with the previous two rows

Transition equation: dp[i][j][k] = max(dp[i][j][k], dp[i-1][k][t] + num[j]), where num[j] is the number of cannons in state j.

Implementation

import sys

def solve():
    n, m = map(int, sys.stdin.readline().split())
    grid = [sys.stdin.readline().strip() for _ in range(n)]
    
    # Precompute valid row states
    valid_states = []
    for state in range(1 << m):
        # Check horizontal adjacency (1 and 2 cells apart)
        if state & (state << 1) or state & (state << 2):
            continue
        valid_states.append(state)
    
    # Count cannons in each valid state
    cannon_count = [bin(state).count('1') for state in valid_states]
    
    # Map grid to bitmasks (1 = mountain)
    terrain = []
    for row in grid:
        mask = 0
        for j in range(m):
            if row[j] == 'H':
                mask |= (1 << (m - 1 - j))
        terrain.append(mask)
    
    # Initialize DP table
    dp = [[[-1] * len(valid_states) for _ in range(len(valid_states))] for _ in range(n+1)]
    
    # Initialize first row
    for j in range(len(valid_states)):
        if valid_states[j] & terrain[0] == 0:  # Compatible with terrain
            dp[1][j][0] = cannon_count[j]
    
    # Fill DP table
    for i in range(2, n+1):
        for j in range(len(valid_states)):
            if valid_states[j] & terrain[i-1] != 0:
                continue  # Incompatible with terrain
            for k in range(len(valid_states)):
                if valid_states[j] & valid_states[k] != 0:
                    continue  # Conflict with previous row
                for t in range(len(valid_states)):
                    if valid_states[k] & valid_states[t] != 0:
                        continue  # Conflict in previous two rows
                    if dp[i-1][k][t] != -1:
                        dp[i][j][k] = max(dp[i][j][k], dp[i-1][k][t] + cannon_count[j])
    
    # Find maximum
    max_cannons = 0
    for j in range(len(valid_states)):
        for k in range(len(valid_states)):
            max_cannons = max(max_cannons, dp[n][j][k])
    
    return max_cannons

print(solve())

Non-attacking Kings Problem

Place kings on an N×N chessboard such that no two kings attack each other. Kings can attack adjacent cells (including diagonals). We need to count the number of ways to place exactly K kings.

Approahc

This problem also uses state compression DP. We represent each row's king placement as a bitmask and ensure:

1. No two kings in adjacent cells within the same row
2. No kings in adjacent cells between consecutive rows The DP state dp[i][j][k] represents the number of ways to place kings in the first i rows, where row i has state j and contains k kings.

Transition: dp[i][j][k] += dp[i-1][prev_state][k - count(j)], where prev_state is compatible with j.

Implementation

def solve_non_attacking_kings():
    n, k = map(int, sys.stdin.readline().split())
    
    # Precompute valid row states
    valid_states = []
    for state in range(1 << n):
        # No adjacent kings in same row
        if (state & (state << 1)) == 0:
            valid_states.append(state)
    
    # Count kings in each valid state
    king_count = [bin(state).count('1') for state in valid_states]
    
    # Initialize DP table
    dp = [[[0] * (k+1) for _ in range(len(valid_states))] for _ in range(n+1)]
    dp[0][0][0] = 1
    
    # Fill DP table
    for i in range(1, n+1):
        for j in range(len(valid_states)):
            current_state = valid_states[j]
            current_kings = king_count[j]
            for prev in range(len(valid_states)):
                prev_state = valid_states[prev]
                # Check compatibility between rows
                if (current_state & prev_state) or (current_state & (prev_state << 1)) or (current_state & (prev_state >> 1)):
                    continue
                for cnt in range(k+1):
                    if cnt >= current_kings:
                        dp[i][j][cnt] += dp[i-1][prev][cnt - current_kings]
    
    # Sum up all valid configurations for the last row
    result = 0
    for j in range(len(valid_states)):
        result += dp[n][j][k]
    
    return result

print(solve_non_attacking_kings())