| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 50 | 29 | 27 | 79.412% |
Given a grid $A$ of size $N \times M$. Each row is numbered from 1ドル$ to $N,ドル and each column is numbered from 1ドル$ to $M$. The cell at row $r$ and column $c$ is denoted as $(r, c)$.
Cell $(r, c)$ contains an integer $A_{r,c},ドル which can be either $-1$ or a non-negative integer. If $A_{r,c} = -1,ドル that means cell $(r, c)$ is impassable. Otherwise, cell $(r, c)$ is passable.
Two players will alternately take turns playing on this grid. In one turn, a player will do the following.
A player who is unable to play on his turn (i.e. no positive integer on his turn) loses the game, and the opposing player wins the game.
If both players play optimally, determine who will win the game.
Input begins with two integers $N$ $M$ (1ドル ≤ N, M ≤ 500$) representing the size of grid $A$. Each of the next $N$ lines contains $M$ integers $A_{r,c}$ (0ドル ≤ A_{r,c} ≤ 10^9$ or $A_{r,c} = -1$) representing the integer contained in cell $(r, c)$.
If the first player win the game, output first in a single line. Otherwise, output second in a single line.
5 6 0 0 0 0 0 0 0 3 3 0 0 0 0 0 3 -1 0 0 0 0 3 3 3 3 0 0 -1 -1 -1 -1
first
The first player can start his turn from $(2, 2)$ and choose $y = 0$. Then, he can keep following the cells with integer 3ドル$ and update those cells to 3ドル \oplus 3 \oplus 0 = 0$. After the first turn, there is no positive integer on the grids, thus second player is unable to play.
2 2 1 1 2 -1
first
There are 5ドル$ options that can be made by the first player during the first turn, as shown in the following illustration. Each option has different starting cell (abbreviated as SC), the value of $y,ドル and the path taken by the first player. The taken paths are indicated by the red shaded cells.
1 1 -1
second
The initial grid has no positive integer cell. The second player wins the game by default.