시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 | 512 MB | 44 | 31 | 20 | 71.429% |
JOI 君は IOI の懇親会に参加している.懇親会ではサンドイッチが縦 R 行,横 C 列の正方形のマス目に 沿って配置されていた.サンドイッチは 2 辺がマス目の 1 辺の長さに等しい直角二等辺三角形の形をして おり,それぞれのマスには 2 個のサンドイッチが斜辺が接するように置かれている.下図はサンドイッチ の配置の例を表している.
図 1. サンドイッチの配置の例
以下の 2 つの条件を同時に満たすサンドイッチは,取ることができない.
これ以外のサンドイッチは取ることができる.
サンドイッチが全く取られていない状態を初期状態とする.初期状態から,あるサンドイッチを取るた めには,他のいくつかのサンドイッチを取らなければいけないかもしれない.サンドイッチの配置によっ ては,取ることができないサンドイッチもあるかもしれない.
JOI 君は,同じマスに置かれている 2 個のサンドイッチを両方とも食べたいと思っている.どのマスに 置かれているサンドイッチを食べるかは,まだ決めていない.
初期状態から,あるマスの 2 個のサンドイッチを両方取るときに,取らなければならないサンドイッチ の個数の最小値が気になる.
サンドイッチの配置が与えられたとき,それぞれのマスについて,そのマスの 2 個のサンドイッチを,初 期状態からいくつかのサンドイッチを取ることによって両方取ることができるか判定し,もし取ることが できる場合は取る必要のあるサンドイッチの個数の最小値を求めるプログラムを作成せよ.ただし,サン ドイッチの個数には,目的の 2 個のサンドイッチも含めて数える.
標準入力から以下のデータを読み込め.
図 2. 各マスのサンドイッチの配置
標準出力に R 行で出力せよ.i 行目 (1 ≦ i ≦ R) には,C 個の整数を空白を区切りとして出力せよ.j 番目 (1 ≦ j ≦ C) の整数として,上から i 行目,左から j 列目のマスのサンドイッチ 2 個を両方取るときに取る 必要があるサンドイッチの個数の最小値を出力せよ.もし,取ることができない場合は,−1 を出力せよ.
追加の制限はない.
2 3 NZN ZZN
10 8 2 8 6 4
例えば,上から 2 行目,左から 2 列目のマスの 2 個のサンドイッチを取るには,以下の順にサンドイッ チを取っていけばよい.
合計で 6 個のサンドイッチを取ることになり,これが最小であるため 6 を出力する.
2 2 NZ ZN
-1 -1 -1 -1
5 5 NZZZN NNNZN NNZNN NZNNN NZZZN
10 12 14 16 2 8 -1 -1 -1 4 6 -1 -1 -1 6 4 -1 -1 -1 8 2 16 14 12 10