Generalized tic-tac-toe with k in a row

Design a two-player Tic-Tac-Toe game on a board with n rows and m columns. A player wins by placing k of their own marks consecutively in one line: horizontal, vertical, diagonal, or anti-diagonal.

Implement the class TicTacToe:

• TicTacToe(n: int, m: int, k: int) creates an empty n x m board with win length k (1 <= k <= max(n, m)).
• move(row: int, col: int, player: int) -> int places a mark for player (1 or 2) on the empty cell (row, col) and returns:
  • 0 if nobody has won yet,
  • 1 or 2 if this move wins the game for that player.

Rules:

1. Every move is on an empty, in-bounds cell. Validating this is still good practice.
2. The game ends at the first win. After that, no more moves are allowed.
3. The marks must be adjacent. A row with k marks of one player that has a gap is not a win.

Unlike the classic version, k may be smaller than the board's sides, so a win does not have to fill a whole row, column or diagonal. Aim for a move that is faster than rescanning the board.

Constraints: 1 <= n, m <= 1000, 1 <= k <= max(n, m), at most n * m calls to move.

Example 1

game = TicTacToe(4, 5, 3)
game.move(3, 0, 1)  # 0
game.move(0, 4, 2)  # 0
game.move(2, 1, 1)  # 0
game.move(0, 3, 2)  # 0
game.move(1, 2, 1)  # 1  -> (3,0), (2,1), (1,2) form an anti-diagonal of length 3

Example 2

game = TicTacToe(1, 5, 3)
game.move(0, 0, 1)  # 0
game.move(0, 1, 1)  # 0
game.move(0, 3, 1)  # 0  -> three marks in the row, but not consecutive
game.move(0, 2, 1)  # 1  -> columns 0..3 are now one run of 4 >= 3

(Player turns are not enforced in Example 2, to keep it short.)

Follow-up: Can you report a draw when the board fills up without a winner?