2152. The Move That Completes the Line

An r by c board starts empty. A list of q moves is played in the order given, numbered 1 to q. Each move names the player, 1 or 2, and a row and a column.

Three rules settle everything a casual description of such a game leaves open:

1. a move onto a square that already holds a mark is ILLEGAL. The board does not change, and the move still uses up its number. 2. turns are NOT enforced. The player named on each move is the player who moves, even if the same player moves twice running. 3. the game ends the instant a player has w of their own marks in a row horizontally, vertically, or along either diagonal. Later moves in the list are not played.

Print the winning player and the number of the move that ended the game, separated by a space. If no player ever completes a line, print DRAW.

``` r = 3, c = 3, w = 3, moves: 1 1 0 0 2 2 1 1 3 1 0 1 4 2 2 2 5 1 0 2 -> 1 5

player 1 holds (0,0), (0,1) and (0,2) after move 5, which is the top row ```

``` r = 3, c = 3, w = 3, moves: 1 1 1 1 2 1 1 1 3 1 0 0 4 1 2 2 -> 1 4

move 2 is illegal, since (1,1) is taken, and it still consumes move number 2, so the diagonal is completed on move 4 and not on move 3 ```

## What most people try first

Rescanning the entire board after every move, looking for any line of w. It is correct, and it is the second implementation used to verify this problem, but it costs O(r c w) per move, and only one square has changed.

The sharper version counts outward from the square just played, which is the only square that can be part of a newly completed line:

for each of the four directions (0,1), (1,0), (1,1), (1,-1): run = 1 walk forward from the played square while the mark matches, counting walk backward from the played square while the mark matches, counting if run >= w: the mover has won

Four directions, not eight: walking both ways along each of them already covers all eight compass headings, and doing eight directions separately double-counts the played square and reports lines that are half the length.

## Why counting from the played square is enough

Before the move, no line of w existed, or the game would already have ended. After the move, suppose the mover has a line of w. Every square of that line holds the mover's mark, and the board before the move differed from the board after it in exactly one square, the one just played. If that square were not on the line, the line would have been complete before the move as well, which contradicts the game not having ended. So the played square lies on the line, and the line runs in one of the four directions through it. Walking both ways from the played square along that direction counts a maximal run of the mover's marks containing the line, so the count is at least w and the win is found.

The run >= w rather than run == w matters: the run through the played square may be longer than w, for instance when the move joins two existing runs. An equality test misses exactly that case.

## The boundary that breaks a careless implementation

An illegal move must not be skipped silently in the numbering. It consumes its move number, so the answer is a different number from the one a solution that only counts legal moves would print. The second worked example above is precisely that case and is a declared test.

w may be 1, which means the first legal move wins. w may also be larger than both r and c, which means no line can ever be completed and the answer is always DRAW.

## Cost

O(w) per move for the four directions, so O(q w) overall, plus O(r c) memory for the board.

Constraints - `1 ≤ r, c ≤ 50` - `1 ≤ w ≤ 50` - `1 ≤ q ≤ 2000` - the player on each move is 1 or 2 - `0 ≤ row < r` and `0 ≤ column < c` - a move onto an occupied square is illegal, changes nothing, and still consumes its move number - turns are not enforced - the game stops at the move that completes a line, and the remaining moves are not played