P2472 [SCOI2007] Lizard

On an $r$-row $c$-column grid map, there are stone pillars of varying heights. The pillar at row $i$, column $j$ has height $h_{i,j}$. Some pillars have lizards standing on them. Your task is to let as many lizards as possible escape outside the boundary. The distance between adjacent pillars in the same row or column is $1$. Each lizard has a jump distance of $d$, meaning it can jump to any pillar whose Euclidean distance is at most $d$. The pillars are unstable. Each time a lizard jumps, the height of the pillar it leaves decreases by $1$ (if it still lands inside the map, the destination pillar’s height does not change). If that pillar’s original height is $1$, then after a lizard leaves, the pillar disappears, and no other lizard can land on it thereafter. At any time, no two lizards may stand on the same pillar.

The first line contains three integers $r, c, d$, which are the map size and the maximum jump distance. The next $r$ lines each contain $c$ numbers describing the initial state of the pillars: $0$ means there is no pillar, otherwise it is the initial height $h_{i,j}$. The next $r$ lines each contain $c$ characters describing lizard positions: `L` means a lizard, and `.` means no lizard.

Output a single line containing one integer, which is the minimum total number of lizards that cannot escape.

For $100\%$ of the testdata: $1 \le r, c \le 20$, $1 \le d \le 4$, $1 \le h \le 3$. Translated by ChatGPT 5