OA: K-in-a-row with validation and undo

Build a two-player game of generalised tic-tac-toe. The board has n rows and m columns (rows 0..n-1, columns 0..m-1), and a player wins by owning k cells in an unbroken straight line: along a row, along a column, or along either diagonal (down-right \ or down-left /). A line of more than k also counts.

Implement TicTacToe(n, m, k) with 1 <= k <= max(n, m):

• move(row, col, player) -> int: player 1 or 2 claims the cell. Return player if this move gives them k in a line, otherwise 0.

For this level every move is legal: players alternate starting with player 1, each move is on an empty cell inside the board, and no move is made after someone has won.

g = TicTacToe(3, 5, 4)
g.move(1, 0, 1)   # 0
g.move(0, 0, 2)   # 0
g.move(1, 1, 1)   # 0
g.move(0, 4, 2)   # 0
g.move(1, 3, 1)   # 0    row 1 is X X . X: the gap breaks the line
g.move(2, 2, 2)   # 0
g.move(1, 2, 1)   # 1    row 1, columns 0-3

g = TicTacToe(4, 4, 3)
g.move(0, 2, 1)   # 0
g.move(0, 0, 2)   # 0
g.move(1, 1, 1)   # 0
g.move(3, 3, 2)   # 0
g.move(2, 0, 1)   # 1    down-left diagonal (0,2) (1,1) (2,0)

Boards can be large (up to 1000 by 1000) and games long. Don't rescan the board after each move: only lines through the new cell can have changed, and in each of the four directions you only need to walk at most k - 1 cells each way. So a move should cost O(k), not O(n * m).