以下页面来自日本信息收集官方发布的原题PDF,已完整保存并渲染到本地。



可复制的 PDF 提取文本
Japanese Olympiad in Informatics 2015/2016
Spring Training Camp/Qualifying Trial
March 19–25, 2016, Komaba/Yoyogi, Tokyo
Contest Day 2 – Sandwich
サンドイッチ(Sandwich)
JOI 君はIOI の懇親会に参加している.懇親会ではサンドイッチが縦R 行,横C 列の正方形のマス目に
沿って配置されていた.サンドイッチは2 辺がマス目の1 辺の長さに等しい直角二等辺三角形の形をして
おり,それぞれのマスには2 個のサンドイッチが斜辺が接するように置かれている.下図はサンドイッチ
の配置の例を表している.
図1. サンドイッチの配置の例
以下の2 つの条件を同時に満たすサンドイッチは,取ることができない.
• 斜辺が,まだ取られていない他のサンドイッチに接している.
• 斜辺以外の2 本の辺のうち少なくとも1 本が,まだ取られていない他のサンドイッチに接している.
これ以外のサンドイッチは取ることができる.
サンドイッチが全く取られていない状態を初期状態とする.初期状態から,あるサンドイッチを取るた
めには,他のいくつかのサンドイッチを取らなければいけないかもしれない.サンドイッチの配置によっ
ては,取ることができないサンドイッチもあるかもしれない.
JOI 君は,同じマスに置かれている2 個のサンドイッチを両方とも食べたいと思っている.どのマスに
置かれているサンドイッチを食べるかは,まだ決めていない.
初期状態から,あるマスの2 個のサンドイッチを両方取るときに,取らなければならないサンドイッチ
の個数の最小値が気になる.
課題
サンドイッチの配置が与えられたとき,それぞれのマスについて,そのマスの2 個のサンドイッチを,初
期状態からいくつかのサンドイッチを取ることによって両方取ることができるか判定し,もし取ることが
できる場合は取る必要のあるサンドイッチの個数の最小値を求めるプログラムを作成せよ.ただし,サン
ドイッチの個数には,目的の2 個のサンドイッチも含めて数える.
サンドイッチ– 1 / 3
Japanese Olympiad in Informatics 2015/2016
Spring Training Camp/Qualifying Trial
March 19–25, 2016, Komaba/Yoyogi, Tokyo
Contest Day 2 – Sandwich
入力
標準入力から以下のデータを読み込め.
• 1 行目には,整数R,C が空白を区切りとして書かれている.これらは,サンドイッチが縦R 行,横
C 列の正方形のマス目に沿って配置されていることを表す.
• 続くR 行のうちのi 行目(1 ≦i ≦R) には,C 文字からなる文字列が書かれている.各文字は‘N’ ま
たは‘Z’ である.この文字列の左からj 文字目(1 ≦j ≦C) は,上からi 行目,左からj 列目のマス
のサンドイッチの配置を表している.‘N’, ‘Z’ はそれぞれ以下のような配置を表している.
図2. 各マスのサンドイッチの配置
出力
標準出力にR 行で出力せよ.i 行目(1 ≦i ≦R) には,C 個の整数を空白を区切りとして出力せよ.j 番目
(1 ≦j ≦C) の整数として,上からi 行目,左からj 列目のマスのサンドイッチ2 個を両方取るときに取る
必要があるサンドイッチの個数の最小値を出力せよ.もし,取ることができない場合は,−1 を出力せよ.
制限
すべての入力データは以下の条件を満たす.
• 1 ≦R ≦400.
• 1 ≦C ≦400.
小課題
小課題1 [35 点]
以下の条件を満たす.
• R ≦50.
• C ≦50.
サンドイッチ– 2 / 3
Japanese Olympiad in Informatics 2015/2016
Spring Training Camp/Qualifying Trial
March 19–25, 2016, Komaba/Yoyogi, Tokyo
Contest Day 2 – Sandwich
小課題2 [65 点]
追加の制限はない.
入出力例
入力例1 出力例1
2 3 10 8 2
NZN 8 6 4
ZZN
入力例1 のサンドイッチの配置は,問題文中の図1 に対応する.
例えば,上から2 行目,左から2 列目のマスの2 個のサンドイッチを取るには,以下の順にサンドイッ
チを取っていけばよい.
• 上から1 行目,左から3 列目のマスの右上のサンドイッチを取る.
• 上から1 行目,左から3 列目のマスの左下のサンドイッチを取る.
• 上から2 行目,左から3 列目のマスの右上のサンドイッチを取る.
• 上から2 行目,左から3 列目のマスの左下のサンドイッチを取る.
• 上から2 行目,左から2 列目のマスの右下のサンドイッチを取る.
• 上から2 行目,左から2 列目のマスの左上のサンドイッチを取る.
合計で6 個のサンドイッチを取ることになり,これが最小であるため6 を出力する.
入力例2 出力例2
2 2 -1 -1
NZ -1 -1
ZN
この場合,いずれのサンドイッチも取ることができない.
入力例3 出力例3
5 5 10 12 14 16 2
NZZZN 8 -1 -1 -1 4
NNNZN 6 -1 -1 -1 6
NNZNN 4 -1 -1 -1 8
NZNNN 2 16 14 12 10
NZZZN
サンドイッチ– 3 / 3