最大連結成分(4 x 4)
(paizaランク A 相当)
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
シェア用URL:
ツイートする
問題
下記の問題をプログラミングしてみよう！
(電脳言語のオルダーソンループで出題された問題のヒント問題です。8 言語での解答コードと解説が用意されています。)
縦に 4 マス、横に 4 マスの長さの二次元グリッドが与えられます。それぞれのセルには、正負両方の値をとる整数が与えられます。
このグリッドから連結したセルの集合を選んだ時、その集合のスコアを、セルに書かれた整数の和と定義します。 ただし、セルの集合が連結であるとは、セル集合内のある一つのセルから、上下左右に繋がっている集合内のセルを辿ることで、集合内の全てのセルを辿れることを指します。 例えば、下の図では、黒いセルの集合は、左の 2 つの例では連結であり、右の 2 つの例では連結ではありません。
あなたは、適切な連結したセルの集合を選ぶことによって、スコアを最大化しようと考えました。 適切なセルを選択することによって、スコアを最大化してください。
- 入力される値
-
g_{1, 1} g_{1, 2} g_{1, 3} g_{1, 4}
g_{2, 1} g_{2, 2} g_{2, 3} g_{2, 4}
g_{3, 1} g_{3, 2} g_{3, 3} g_{3, 4}
g_{4, 1} g_{4, 2} g_{4, 3} g_{4, 4}
・ i (1 ≦ i ≦ 4) 行目の j (1 ≦ i ≦ 4) 番目の整数は、グリッドの i 行 j 列目のセルに書かれている整数を表します。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
・ 期待する出力は 4 行になります。
・ それぞれの行の出力は長さ 4 の 0 または 1 からなる文字列になります。
・ i 行目 j 列目 (1 ≦ i ≦ 4, 1 ≦ j ≦ 4) を連結成分に含める場合は 1 を、含めない場合は 0 を出力してください。
・ 末尾に改行を入れ、余計な文字、空行を含んではいけません。
- 条件
-
全てのテストケースにおいて, 以下の条件を満たします。
・ -1,000 ≦ g_{i, j} ≦ 1,000 (1 ≦ i ≦ 4, 1 ≦ j ≦ 4)
- 入力例1
-
-7 5 8 2
0 -11 9 12
4 -7 -5 -11
-8 1 3 9
- 出力例1
-
0111
0011
0010
0111
