No.3596 Queen Score Attack 1
タグ : / 解いたユーザー数 63
作問者 : 👑
gomaazarasi
UT0911
ぽえ
問題文
縦 $H$ マス，横 $W$ マスのマス目があります．上から $i(1 \leq i \leq H)$ 番目，左から $j(1 \leq j \leq W)$ 番目のマスを，マス $(i, j)$ と表記します．
各マスには整数が書かれています．マス $(i, j)$ に書かれている整数は $A_{i, j}$ です．
このマス目上で，クイーンのコマを動かします．クイーンのコマは，マス目の範囲内のマスに自由に出入り可能ですが，範囲外のマスには出入りできません．
あなたは，これから以下に示す手続きを行います．
- まず，マス目の範囲内の好きなマスを $1$ つ選び，そのマスにクイーンのコマを置く．そのマスに書かれている整数のぶんのスコアを得る．
- 次に，以下を $0$ 回以上好きな回数繰り返す．
- 今クイーンのコマが置かれているマスから $1$ 回の移動で到達できるマスを $1$ つ選び，そのマスにコマを移動させる．移動先のマスに書かれている整数のぶんのスコアを得る．
なお，同じマスを複数回訪れることも許されます（複数回訪れた場合，訪れるごとにスコアを得ます）．
この手続きによって得られるスコアの合計の最大値が存在するか判定してください．
$T$ 個のテストケースが与えられるので，それぞれについて答えてください．
クイーンのコマの移動方法について（クリックで開く）
クイーンのコマは，$1$ 回の移動において，縦・横・斜めの方向に，通る経路のマスが全て出入り可能である限り自由なマス数進むことができます．ただし，今いるマスにとどまることを $1$ 回の移動とみなすことはできません．厳密には，マス $(i, j)$ にあるクイーンのコマは次のような移動が可能です．
- 正整数 $k$ に対し，次の条件を満たしている場合，またそのときに限りマス $(i, j + k)$ への移動が可能である．
- $1 \leq l \leq k$ を満たす全ての整数 $l$ に対し，マス $(i, j + l)$ はクイーンのコマが出入り可能なマスである．
- 正整数 $k$ に対し，次の条件を満たしている場合，またそのときに限りマス $(i, j - k)$ への移動が可能である．
- $1 \leq l \leq k$ を満たす全ての整数 $l$ に対し，マス $(i, j - l)$ はクイーンのコマが出入り可能なマスである．
- 正整数 $k$ に対し，次の条件を満たしている場合，またそのときに限りマス $(i + k, j)$ への移動が可能である．
- $1 \leq l \leq k$ を満たす全ての整数 $l$ に対し，マス $(i + l, j)$ はクイーンのコマが出入り可能なマスである．
- 正整数 $k$ に対し，次の条件を満たしている場合，またそのときに限りマス $(i - k, j)$ への移動が可能である．
- $1 \leq l \leq k$ を満たす全ての整数 $l$ に対し，マス $(i - l, j)$ はクイーンのコマが出入り可能なマスである．
- 正整数 $k$ に対し，次の条件を満たしている場合，またそのときに限りマス $(i + k, j + k)$ への移動が可能である．
- $1 \leq l \leq k$ を満たす全ての整数 $l$ に対し，マス $(i + l, j + l)$ はクイーンのコマが出入り可能なマスである．
- 正整数 $k$ に対し，次の条件を満たしている場合，またそのときに限りマス $(i + k, j - k)$ への移動が可能である．
- $1 \leq l \leq k$ を満たす全ての整数 $l$ に対し，マス $(i + l, j - l)$ はクイーンのコマが出入り可能なマスである．
- 正整数 $k$ に対し，次の条件を満たしている場合，またそのときに限りマス $(i - k, j + k)$ への移動が可能である．
- $1 \leq l \leq k$ を満たす全ての整数 $l$ に対し，マス $(i - l, j + l)$ はクイーンのコマが出入り可能なマスである．
- 正整数 $k$ に対し，次の条件を満たしている場合，またそのときに限りマス $(i - k, j - k)$ への移動が可能である．
- $1 \leq l \leq k$ を満たす全ての整数 $l$ に対し，マス $(i - l, j - l)$ はクイーンのコマが出入り可能なマスである．
制約
- 入力は全て整数
- $1 \leq T$
- $2 \leq H \leq 100$
- $2 \leq W \leq 100$
- $-10^9 \leq A_{i, j} \leq 10^9$
- $1$ つの入力ファイルにおける $HW$ の総和は $10^4$ 以下
入力
入力は以下の形式で標準入力から与えられる．ここで，$\mathrm{case}_i$ は $i$ 番目のテストケースを表す．
$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$
各ケースは以下の形式で与えられる．
$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}$
出力
$T$ 行出力せよ．$i$ 行目には，$i$ 番目のテストケースにおいて最大値が存在するならば finite を，存在しないならば infinite を出力せよ．
サンプル
サンプル1
入力
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
出力
infinite finite infinite
$1$ 個目のテストケースについて，例えば最初マス $(1, 1)$ にクイーンのコマを置き，$(1, 1) \rightarrow (1, 2) \rightarrow (2, 2) \rightarrow (2, 3)$ の順に移動させた場合のスコアは，$1 + 2 + 5 + 6 = 14$ となります．
このテストケースでは，適切にコマを移動させることでスコアの値をいくらでも大きくできることが示せます．したがって，得られるスコアの最大値は存在しません．
$2$ 個目のテストケースについて，どのように手続きを行ってもスコアの値は $0$ から変化しません．したがって，得られるスコアの最大値は $0$ となります．
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。