All problems

Blind-Spot Guards

Medium · backtracking

A museum floor is a grid of squares. The list plan has one string per row. In each string, . is open floor and # is a wall.

You must place exactly k guards, each standing on a different open square. A guard can see straight along their row and along their column, in both directions, until the line of sight reaches a wall or the edge of the floor. Guards do not block each other's view. A layout is safe when no guard can see another guard.

Return how many safe layouts there are. Two layouts are different if some square holds a guard in one and not in the other (the guards themselves are not told apart). Return 0 if there is no safe layout.

Examples

Example 1

Input: plan = ["..", ".."], k = 2

Output: 2

The guards must be on opposite corners, and there are two such pairs.

Example 2

Input: plan = ["..#.."], k = 2

Output: 4

One guard stands on each side of the wall, so there are 2 * 2 = 4 layouts. Two guards on the same side see each other.

Example 3

Input: plan = ["...", ".#.", "..."], k = 3

Output: 8

Constraints

• 1 <= len(plan) <= 6
• 1 <= len(plan[i]) <= 6, and every row has the same length
• plan[i] contains only the characters . and #
• 1 <= k <= 8