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



可复制的 PDF 提取文本
The 19th Japanese Olympiad in Informatics (JOI 2019/2020)
JOI Open Contest
September 6, 2020
furniture
家具の配置(Furniture)
JOI 君の部屋は長方形状の形をしており,縦N 行,横M 列の区画に区切られている.部屋の縦方向は南
北方向に平行であり,横方向は東西方向に平行である.北からi 行目,西からj 列目(1 ≦i ≦N, 1 ≦j ≦M)
にある区画を区画(i, j) と書く.この部屋のいくつかの区画には家具が置かれている.区画(i, j) (1 ≦i ≦N,
1 ≦j ≦M) にはCi, j = 1 のとき家具が置いてあり,Ci, j = 0 のときは家具は置かれていない.
区画(1, 1) から南方向または東方向に隣接する区画に移動することを繰り返して,家具の置いてある区画
を通らずに区画(N, M) に到達できるとき,そのような家具の配置を良い配置と呼ぶ.家具の初期配置は良
い配置であることが保証されている.
これからJOI 君はQ 回の作業を行う.k 番目の作業(1 ≦k ≦Q) は次のように行われる.
区画(Xk, Yk) に家具を置いてもなお家具の配置が良い配置となる場合,区画(Xk, Yk) に家具を置く.
そうでない場合は何もしない.
ただし,最初から家具が置かれている区画や一度作業を行った区画で再び作業を行うことはない.また,
区画(1, 1) および区画(N, M) に最初から家具が置かれていることはなく,そこで作業を行うこともない.部
屋の大きさ,家具の初期配置,各作業を行う区画が与えられたとき,各作業で家具が置かれるかを判定する
プログラムを作成せよ.
入力
入力は以下の形式で標準入力から与えられる.入力される値はすべて整数である.
N M
C1,1 C1,2 · · · C1,M
C2,1 C2,2 · · · C2,M
...
CN,1 CN,2 · · · CN,M
Q
X1 Y1
X2 Y2
...
XQ YQ
家具の配置– 1 / 3
The 19th Japanese Olympiad in Informatics (JOI 2019/2020)
JOI Open Contest
September 6, 2020
furniture
出力
標準出力にQ 行で出力せよ.k 行目(1 ≦k ≦Q) には,k 番目の作業で区画(Xk, Yk) に家具が置かれる場
合は1 を,そうでない場合は0 を出力せよ.
制約
• 1 ≦N ≦1 000.
• 1 ≦M ≦1 000.
• 0 ≦Ci, j ≦1 (1 ≦i ≦N, 1 ≦j ≦M).
• C1,1 = 0.
• CN,M = 0.
• 家具の初期配置は良い配置である.
• 1 ≦Q ≦N × M.
• 1 ≦Xk ≦N (1 ≦k ≦Q).
• 1 ≦Yk ≦M (1 ≦k ≦Q).
• (Xk, Yk) , (1, 1) (1 ≦k ≦Q).
• (Xk, Yk) , (N, M) (1 ≦k ≦Q).
• CXk,Yk , 1 (1 ≦k ≦Q).
• (Xk, Yk) , (Xl, Yl) (1 ≦k < l ≦Q).
小課題
1. (5 点) N ≦100, M ≦100.
2. (95 点) 追加の制約はない.
家具の配置– 2 / 3
The 19th Japanese Olympiad in Informatics (JOI 2019/2020)
JOI Open Contest
September 6, 2020
furniture
入出力例
入力例1 出力例1
2 3 0
0 0 1 1
0 0 0 0
3
2 2
2 1
1 2
1 番目の作業は区画(2, 2) で行われる.区画(2, 2) に家具を置くと良い配置ではなくなるため,実際には
家具を置かない.よって出力すべき値は0 となる.
2 番目の作業は区画(2, 1) で行われる.区画(2, 1) に家具を置いたとき,例えば(1, 1), (1, 2), (2, 2), (2, 3)
の順に区画を移動することができるため,家具の配置は良い配置となる.よって区画(2, 1) には家具が置か
れ,出力すべき値は1 となる.
3 番目の作業は区画(1, 2) で行われる.すでに区画(2, 1) に家具が置かれているため,区画(1, 2) に家具を
置くと良い配置ではなくなる.よって出力すべき値は0 となる.
入力例2 出力例2
2 5 0
0 0 0 0 0 1
0 0 0 1 0
2
1 2
2 2
1 番目の作業は区画(1, 2) で行われる.区画(1, 2) に家具を置くと良い配置ではなくなるため,実際には
家具を置かない.よって出力すべき値は0 となる.(1, 1), (2, 1), (2, 2), (2, 3), (1, 3), (1, 4), (1, 5), (2, 5) の順
の区画の移動は家具の置いてある区画を通らないが,(2, 3) から(1, 3) への移動が北方向であるため良い配
置の条件に該当しないことに注意せよ.
2 番目の作業は区画(2, 2) で行われる.区画(2, 2) に家具を置いたとき,例えば(1, 1), (1, 2), (1, 3), (1, 4),
(1, 5), (2, 5) の順に区画を移動することができるため,家具の配置は良い配置となる.よって区画(2, 2) には
家具が置かれ,出力すべき値は1 となる.
家具の配置– 3 / 3