ネット・ガーディアンの奮闘 Java編（paizaランク A 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
下記の問題をプログラミングしてみよう！
(電脳言語のオルダーソンループで出題された問題です。8 言語での解答コードと解説が用意されています。)
縦に H マス、横に W マスの長さの二次元グリッドが与えられます。 それぞれのセルには、正負両方の値をとる整数が与えられます。
このグリッドから連結したセルの集合を選んだとき、その集合のスコアを、セルに書かれた整数の和と定義します。 ただし、セルの集合が連結であるとは、セル集合内のある一つのセルから、上下左右につながっている集合内のセルをたどることで、集合内のすべてのセルをたどれることを指します。 例えば、下の図では、黒いセルの集合は、左の 2 つの例では連結であり、右の 2 つの例では連結ではありません。
あなたは、適切な連結したセルの集合を選ぶことによって、スコアを最大化しようと考えました。 適切なセルを選択することによって、スコアを可能な限り最大化してください。
なおこの問題には、基準となるスコアが設定されています。あなたが選択したセルの集合のスコアが、その基準値以上だった場合に正解となります。
例えば、下の画像は、それぞれの場合におけるスコアを示します。
- 入力される値
-
H W
g_{1, 1} g_{1, 2} ... g_{1, W}
g_{2, 1} g_{2, 2} ... g_{2, W}
...
g_{H, 1} g_{H, 2} ... g_{H, W}
・ 1 行目に二次元グリッドの縦と横の長さを表す整数 H, W が半角スペース区切りで与えられます。
・ 続く H 行のうちの i 行目 (1 ≦ i ≦ H) には、W 個の整数が半角スペース区切りで与えられます。
・ i 行目の j 番目 (1 ≦ j ≦ W) の整数 g_{i, j} はグリッドの i 行 j 列目のセルに書かれている整数を表します。
・ 入力は合計で H + 1 行となり、入力値最終行の末尾に改行が １ つ入ります。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
・ 期待する出力は H 行になります。
・ それぞれの行の出力は長さ W の 0 または 1 からなる文字列になります。
・ i 行目 j 列目 (1 ≦ i ≦ H, 1 ≦ j ≦ W) を連結成分に含める場合は 1 を、含めない場合は 0 を出力してください。
・ 末尾に改行を入れ、余計な文字、空行を含んではいけません。
- 条件
-
すべてのテストケースにおいて, 以下の条件を満たします。
・ H = 30, W = 30 (入力例のみ H, W < 30)
・ -1,000 ≦ g_{i, j} ≦ 1,000
- 入力例1
-
3 3
1 2 3
4 5 6
7 8 9
- 出力例1
-
111
111
111
