State Compression Dynamic Programming: Cannon Positioning and Non-attacking Kings Problems
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
...
Posted on Fri, 17 Jul 2026 16:18:25 +0000 by andymike07