No.3596 Queen Score Attack 1
タグ : / 解いたユーザー数 68
作問者 : 👑
gomaazarasi
UT0911
ぽえ
Problem Statement
There is a grid with $H$ rows and $W$ columns. The cell at the $i(1 \leq i \leq H)$-th row from the top and the $j(1 \leq j \leq W)$-th column from the left is denoted by cell $(i, j)$.
Each cell has an integer written on it. The integer written on cell $(i, j)$ is $A_{i, j}$.
You will move a queen piece on this grid. The queen piece can freely enter and leave cells within the grid, but cannot enter or leave cells outside the grid.
You will now perform the following procedure.
- First, choose any $1$ cell within the grid and place the queen piece on that cell. You gain a score equal to the integer written on that cell.
- Next, repeat the following any number of times, $0$ or more.
- Choose $1$ cell reachable in $1$ move from the cell where the queen piece is currently placed, and move the piece to that cell. You gain a score equal to the integer written on the destination cell.
Note that visiting the same cell multiple times is allowed (if you visit it multiple times, you gain the score on each visit).
Determine whether a maximum value exists for the total score obtainable by this procedure.
You are given $T$ test cases; answer each of them.
About how the queen piece moves (click to open)
In $1$ move, the queen piece can advance any number of cells in a vertical, horizontal, or diagonal direction, as long as all cells on the path can be entered and left. However, staying on the current cell does not count as $1$ move. Strictly speaking, a queen piece on cell $(i, j)$ can make the following moves.
- For a positive integer $k$, it can move to cell $(i, j + k)$ if and only if the following condition is satisfied.
- For every integer $l$ satisfying $1 \leq l \leq k$, cell $(i, j + l)$ is a cell that the queen piece can enter and leave.
- For a positive integer $k$, it can move to cell $(i, j - k)$ if and only if the following condition is satisfied.
- For every integer $l$ satisfying $1 \leq l \leq k$, cell $(i, j - l)$ is a cell that the queen piece can enter and leave.
- For a positive integer $k$, it can move to cell $(i + k, j)$ if and only if the following condition is satisfied.
- For every integer $l$ satisfying $1 \leq l \leq k$, cell $(i + l, j)$ is a cell that the queen piece can enter and leave.
- For a positive integer $k$, it can move to cell $(i - k, j)$ if and only if the following condition is satisfied.
- For every integer $l$ satisfying $1 \leq l \leq k$, cell $(i - l, j)$ is a cell that the queen piece can enter and leave.
- For a positive integer $k$, it can move to cell $(i + k, j + k)$ if and only if the following condition is satisfied.
- For every integer $l$ satisfying $1 \leq l \leq k$, cell $(i + l, j + l)$ is a cell that the queen piece can enter and leave.
- For a positive integer $k$, it can move to cell $(i + k, j - k)$ if and only if the following condition is satisfied.
- For every integer $l$ satisfying $1 \leq l \leq k$, cell $(i + l, j - l)$ is a cell that the queen piece can enter and leave.
- For a positive integer $k$, it can move to cell $(i - k, j + k)$ if and only if the following condition is satisfied.
- For every integer $l$ satisfying $1 \leq l \leq k$, cell $(i - l, j + l)$ is a cell that the queen piece can enter and leave.
- For a positive integer $k$, it can move to cell $(i - k, j - k)$ if and only if the following condition is satisfied.
- For every integer $l$ satisfying $1 \leq l \leq k$, cell $(i - l, j - l)$ is a cell that the queen piece can enter and leave.
Constraints
- All inputs are integers.
- $1 \leq T$
- $2 \leq H \leq 100$
- $2 \leq W \leq 100$
- $-10^9 \leq A_{i, j} \leq 10^9$
- The sum of $HW$ in $1$ input file is at most $10^4$.
Input
The input is given from standard input in the following format. Here, $\mathrm{case}_i$ represents the $i$-th test case.
$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$
Each case is given in the following format.
$H$ $W$
$A_{1, 1}$ $A_{1, 2}$ $\cdots$ $A_{1, W}$
$A_{2, 1}$ $A_{2, 2}$ $\cdots$ $A_{2, W}$
$\vdots$
$A_{H, 1}$ $A_{H, 2}$ $\cdots$ $A_{H, W}$
Output
Print $T$ lines. On the $i$-th line, print finite if the maximum value exists for the $i$-th test case, and infinite if it does not exist.
Sample
Sample 1
Input
3 2 3 1 2 3 4 5 6 3 3 0 0 0 0 0 0 0 0 0 4 4 1 -2 -3 4 -5 -6 -7 -8 -9 -10 -11 -12 13 -14 -15 16
Output
infinite finite infinite
For the $1$st test case, for example, if you initially place the queen piece on cell $(1, 1)$ and move it in the order $(1, 1) \rightarrow (1, 2) \rightarrow (2, 2) \rightarrow (2, 3)$, the score is $1 + 2 + 5 + 6 = 14$.
In this test case, it can be shown that the score can be made arbitrarily large by moving the piece appropriately. Therefore, no maximum value of the obtainable score exists.
For the $2$nd test case, no matter how you perform the procedure, the score does not change from $0$. Therefore, the maximum value of the obtainable score is $0$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。