A house is a grid of R rows and C columns of rooms. Rooms that share a side are joined by a door, and every door can only be passed a limited number of times: the door between room (r, c) and room (r, c + 1) can be passed h[r][c] more times, and the door between room (r, c) and room (r + 1, c) can be passed v[r][c] more times (a count of 0 means there is no usable door). Passing through a door in either direction uses up one passage of that door.
A token is placed in a starting room. Two players then move alternately; a move takes the token through a door of the current room that can still be passed, into the neighbouring room. A player who cannot move loses.
For every room, decide whether the player who makes the first move wins when the token starts in that room and both players play perfectly. Return R strings of length C using 'W' (the first mover wins) and 'L' (the first mover loses).
h has R rows of C - 1 numbers and v has R - 1 rows of C numbers.
Examples
Input: h = [[1, 1]], v = []
Output: ['LWL']
Explanation: from the middle room the first mover walks to an end and the opponent
is stuck. From an end room the opponent answers by walking to the other end.
Input: h = [[1, 1], [1, 1]], v = [[1, 1, 1]]
Output: ['WWW', 'WWW']
Input: h = [[1, 1], [1, 1]], v = [[0, 1, 0]]
Output: ['LWL', 'LWL']
Constraints
1 <= R, C <= 400 <= h[r][c], v[r][c] <= 10**9
Goals
- Reduce door counts to their parities with a mirroring argument
- Characterise winning rooms by linear algebra over GF(2)
- Find all dependent rows with one elimination