In a tile-laying board game, each square of the finished board holds a tile described by two characters: an uppercase land letter (for example F forest, W water, G grass) followed by a digit 0-9, the number of crowns printed on that square. A square may also be "..", meaning no tile was placed there.
Squares with the same land letter that touch up, down, left or right (not diagonally) belong to the same territory. A territory is worth
(number of squares in it) x (total crowns on its squares)
so a territory with no crowns scores nothing. Write board_score(board: list[list[str]]) -> int, the sum over all territories. Empty squares never belong to a territory.
board = [
["F1", "F0", "W0"],
["G0", "F2", "W1"],
["G1", "G0", ".."],
]
board_score(board) # 14
# forest {(0,0),(0,1),(1,1)}: 3 squares x 3 crowns = 9
# water {(0,2),(1,2)}: 2 squares x 1 crown = 2
# grass {(1,0),(2,0),(2,1)}: 3 squares x 1 crown = 3
Details:
- The board is a non-empty rectangle; it can be as large as 500 x 500 and a single territory can cover all of it. Visit each square a constant number of times, and don't use recursion (Python's default limit is about 1,000 frames).
- Two separate territories with the same letter are scored separately:
[["F1", "W0", "F1"]]scores1 + 1 = 2, not2 x 2. - Don't modify
board.
Show hint
Flood-fill each territory once, tracking its size and crowns as you go.