All problems

Lay the Runners

Hard · backtracking

The floor of a small hall is a grid of unit squares. The list floor has one string per row. In each string, . is a bare square and # is a pillar.

You have a set of carpet runners. Each runner is a straight strip, one square wide, and runners[i] is how many squares long it is. A runner lies along a row or along a column and covers that many neighbouring squares in a line. It cannot sit on a pillar or on another runner, and it cannot hang over the edge of the floor.

Every runner must be used exactly once, and every bare square must end up covered. Runners of the same length are identical, so swapping two of them does not make a new layout. A runner of length 1 covers a single square and has no direction. Two layouts are different if the set of strips on the floor is different.

Return how many different layouts there are. Return 0 if there is none.

Examples

Example 1

Input: floor = ["..", ".."], runners = [2, 2]

Output: 2

Either both runners lie along the rows or both stand along the columns.

Example 2

Input: floor = [".#.", "..."], runners = [1, 1, 3]

Output: 1

The long runner must fill the bottom row. The two squares above it are separated by the pillar, so each gets a runner of length 1.

Example 3

Input: floor = ["...", "..."], runners = [3, 3]

Output: 1

Each row takes one runner.

Constraints