#3361. 「JOI Open 2020」家具摆放

内存限制:512 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: HeRaNO

题目描述

译自 JOI Open 2020 T1 「家具の配置 / Furniture

JOI 君房间的形状是矩形,由 N\times M 个单元格组成。这个房间有 N 个横排,每个横排平行于东西方向。有 M 个竖排,每个竖排平行于南北方向。从北数第 i 个,从西数第 j 个格子表示为 (i,j) 格。单元格里放有一些家具。对于 i,j\ (1\le i\le N,1\le j\le M) ,如果 C_{i,j}=1 ,就表示 (i,j) 格中有一件家具。如果 C_{i,j}=0 ,就表示 (i,j) 格中没有家具。

如果我们可以从 (1,1) 出发,只向南或向东走,并且不经过放有家具的格子的情况下到达 (N,M) ,我们就称这种家具摆放方式是好的。保证初始时家具摆放方式是好的。

JOI 君会进行 Q 次操作,第 k\ (1\le k\le Q) 次操作按如下方法进行:

  • 如果一件新家具放置在 (X_k,Y_k) 格中后,家具摆放方式仍然是好的,那么就在 (X_k,Y_k) 格中放一件新家具,否则他不进行操作。

注意,他不会将新家具放在初始有家具或进行过家具摆放操作的格子中。初始 (1,1) (N,M) 格子中不会有家具,并且他不会对这两个格子进行操作。给定房间大小,初始家具摆放情况和他要进行操作的格子,写一个程序确定每次操作会不会进行。

输入格式

第一行两个整数 N,M

接下来 N 行,每行 M 个整数 C_{i,j} ,表示初始家具摆放情况。

接下来一行一个整数 Q ,表示询问次数;

接下来 Q 行,每行两个整数 X_k,Y_k ,表示每次新家具的摆放位置。

输出格式

输出 Q 行到标准输出。第 k\ (1\le k\le Q) 行输出对第 k 次操作的回答。如果 JOI 君可以在 (X_k,Y_k) 格中放一件新家具,则输出 1 ,否则输出 0

样例

样例输入 1

2 3
0 0 1
0 0 0
3
2 2
2 1
1 2

样例输出 1

0
1
0

样例说明 1

第一个操作将新家具放在 (2,2) 。如果 (2,2) 放一件新家具的话,家具摆放方式就不是好的了。因此,JOI 君不会将新家具放在 (2,2) 。输出 0

第二个操作将新家具放在 (2,1) 。如果 (2,1) 放一件新家具的话,按 (1,1),(1,2),(2,2),(2,3) 的顺序就可以从 (1,1) 走到 (2,3) ,家具摆放方式仍然是好的。因此,JOI 君会将新家具放在 (2,1) 。输出 1

第三个操作将新家具放在 (1,2) 。因为 (2,1) 已经放有家具,如果 (2,2) 放一件新家具的话,家具摆放方式就不是好的了。因此,JOI 君不会将新家具放在 (1,2) 。输出 0

样例输入 2

2 5
0 0 0 0 0
0 0 0 1 0
2
1 2
2 2

样例输出 2

0
1

第一个操作将新家具放在 (1,2) 。如果 (1,2) 放一件新家具的话,家具摆放方式就不是好的了。因此,JOI 君不会将新家具放在 (1,2) 。输出 0 。注意如果我们按 (1,1),(2,1),(2,2),(2,3),(1,3),(1,4),(1,5),(2,5) 的顺序仍然可以从 (1,1) 走到 (2,5) ,但是由于从 (2,3) 走到 (1,3) 是向北走,因此不满足好的家具摆放方式的条件。

第二个操作将新家具放在 (2,2) 。如果 (2,2) 放一件新家具的话,按 (1,1),(1,2),(1,3),(1,4),(1,5),(2,5) 的顺序就可以从 (1,1) 走到 (2,5) ,家具摆放方式仍然是好的。因此,JOI 君会将新家具放在 (2,2) 。输出 1

数据范围与提示

对于全部数据, 1\le N,M\le 10^3,0\le C_{i,j}\le 1,1\le Q\le N\times M ,保证:

  • C_{1,1}=C_{N,M}=0
  • 初始家具摆放方式是好的;
  • 1\le X_k\le N,1\le Y_k\le M\ (1\le k\le Q)
  • (X_k,Y_k)\neq (1,1) (X_k,Y_k)\neq (N,M)\ (1\le k\le Q)
  • C_{X_k,Y_k}\neq 1\ (1\le k\le Q)
  • (X_k,Y_k)\neq (X_l,Y_l)\ (1\le k<l\le Q)

详细子任务附加限制及分值如下:

  • 子任务 1 5 分): N,M\le 100
  • 子任务 2 95 分):无附加限制。