Matrix Flower-House Planting Plans
Google● HardNEW GRADONSITE INTERVIEWProblem statement
You are given a rectangular grid containing H (house), F (an existing flower), and O (an empty plot). You may change selected O cells to F; houses and existing flowers cannot be changed.
A final grid is valid when:
- Every row and every column contains at most one flower.
- Every house has exactly one orthogonally adjacent flower.
- Every flower is orthogonally adjacent to exactly one house, so no flower is shared by two houses and no irrelevant flower is planted.
Return every valid final grid. Encode one grid by joining its rows with /, and return the encodings in lexicographic order. Return an empty array when no valid planting exists.
The base interview question asks only whether a valid planting exists. The returned list implements the follow-up that asks for every possible planting; the base answer is true exactly when the returned list is nonempty.
Function
flowerHousePlans(grid: String[]) → String[]Examples
Example 1
grid = ["HOO","OOH"]return = ["HOF/FOH"]The top-left house uses the flower at row 1, column 0, and the bottom-right house uses the flower at row 0, column 2. The flowers occupy different rows and columns.
Example 2
grid = ["HOO","OOO","OOH"]return = ["HFO/OOF/OOH","HOO/FOO/OFH"]There are two valid ways to give each house one exclusive neighboring flower while keeping flower rows and columns unique.
Example 3
grid = ["HFH"]return = []The existing flower touches both houses, so it cannot belong exclusively to either one.
Constraints
1 <= grid.length <= 6.1 <= grid[r].length <= 6, and all rows have equal length.- Every cell is
H,F, orO. - There are at most
10houses. - The number of valid returned grids is at most
10000.