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


可复制的 PDF 提取文本
4 散歩
問題
JOI町に住む太郎君は,ある日,健康増進のために散歩を日課にしようと思い立った.
太郎君の住むJOI 町には,図のように,東西方向に走る(H + 1) 本の道路と,南北
方向に走る(W + 1) 本の道路が碁盤目状に通っている.太郎君の家はもっとも北西の
交差点にあり,ここから散歩を開始する.
以降,北からa 番目,西からb 番目の交差点を(a, b) で表す.たとえば,太郎君の
家がある交差点は(1, 1) である.
(1, 1) (1, W + 1) 家
(H + 1, 1) (H + 1, W + 1)
図: JOI 町の図(H = 3, W = 4 の場合).図の上が北,左が西に対応する.
太郎君は,散歩のルートが日々違ったほうが面白いと考えたので,(1, 1) から(H, W)
までのH × W 個の交差点に,「東」または「南」の文字を書き,次のようなルールに
従って毎日散歩を行うことにした.
• 文字の書かれた交差点にいる場合,その交差点に書かれている文字が「東」な
ら「南」に,「南」なら「東」に文字を書き換え,もともと書かれていた文字の
方角にある次の交差点まで進む.
• もっとも東やもっとも南の道路に到達したら散歩を終了する.
この計画を考えた後,太郎君は,将来の散歩で自分がどのようなルートをたどる
ことになるのかが気になった.太郎君のために,太郎君のN 回目の散歩のルートを
予測するプログラムを作成せよ.
問題4-1
入力
入力ファイルのファイル名はinput.txt である.
1 行目には,3 つの正整数が空白区切りで書かれている.これらは,問題文中の3 つ
の数値H, W, N の値である.H, W, N はそれぞれ,1 ≦H ≦1000, 1 ≦W ≦1000, 1 ≦
N ≦10000000 = 107 をみたす.2 行目からH + 1 行目には,それぞれW 個の整数が
空白区切りで書かれている.これらは,太郎君が最初に交差点に書いた文字の情報
を表す.i + 1 行目のj 番目の整数が0 なら,交差点(i, j) に書かれた文字が「南」で
あることを,1 なら,交差点(i, j) に書かれた文字が「東」であることを表す.
採点用データのうち,配点の30%分については, H ≦100, W ≦100, N ≦1000 を
満たす.
出力
出力ファイルのファイル名はoutput.txt である.
N 回目の散歩において太郎君が散歩を終了する交差点が(i, j) のとき,i とj をこの
順に空白で区切って出力せよ.
入出力の例
例
input.txt
3 4 3
1 0 1 1
0 1 0 0
1 0 1 0
output.txt
1 5
上の例では,1 回目から3 回目の散歩のルートは次の図のようになる.
東 南 東 東 南 東 東 東 東 東 東 東
南 東 南 南 南 南 東 南 東 南 東 南
東 南 東 南 東 南 南 東 南 東 南 東
問題4-2