Moving Chips (Large Input)
Alice and Bob are playing a game called Moving Chips. The game is played on an \(n \times m\) board where some cells have some chips on it. Two players move alternately. Each turn consists of one person moving a chip to any cell to its left or any cell to its top. For example, the possible movements of chip A on a \(3\times 5\) board is:
The last player who moves all the chips to the top left cell wins.
Consider the configuration of a \(100\times 100\) board in this file.
. denotes an empty cell and a digit denotes the number of chips on that cell.
Alice will move first. Assume that both players move optimally, who will win the game?
- The chips can be stacked on top of each other.
- Only one chip may be moved at a time (not a stack), but a chip can move any number of spaces in a single direction (left or up).
- The chips can move passing any chips.