P11972 [JOI Open 2020] 家具摆放 / Furniture

一个房间的布置可以被表示为一个 $n$ 行 $m$ 列的 01 矩阵，其中为 1 的位置表示放置了一件家具，0 表示没有放置。 如果你可以从房间的左上角 $(1,1)$ 只向右和向下走到达右下角 $(n,m)$，且路径上不经过有家具的格子，那么我们定义这样的房间布置是**好的**。 给定房间的初始布置 $C$，对于位置 $(i,j)\ (1\le i \le n, 1\le j \le m)$，$C_{i,j}=1$ 表示有家具，$C_{i,j}=0$ 则没有。保证初始布置一定是**好的**。 现在要进行 $Q$ 次操作，第 $k$ 次操作形如 $(X_k,Y_k)$，表示尝试在 $(X_k,Y_k)$ 处放置一个家具。如果在 $(X_k,Y_k)$ 处放置后整个布置仍然是**好的**，那么就放置这个家具；否则不进行任何操作。对于每次操作，输出这个家具是否被成功放置。 保证尝试放置家具的位置 $(X_k,Y_k)$ 在初始布置和之前的任何一次操作中均没有被放置过家具。保证 $(1,1)$ 和 $(n,m)$ 处没有家具。

第一行两个整数 $n,m$，表示房间的长宽。 接下来是一个 $n\times m$ 的 01 矩阵 $C$，表示房间的初始布置。保证初始布置是**好的**。 接下来是一个整数 $Q$ 表示操作次数。 然后是 $Q$ 行操作，每行给定 $X_k,Y_k$ 两个整数表示尝试放置的位置。

一共 $Q$ 行，第 $k$ 行输出 1 或 0 表示第 $k$ 次操作是否成功放置。如果成功输出 1，否则输出 0。

#### 样例解释 1 第一次操作尝试在 $(2,2)$ 处放置，但放置后 $(1,1)$ 无法到达 $(n,m)$，因此输出 0，不进行任何修改。 第二次操作尝试在 $(2,1)$ 处放置，放置后存在这样一条合法路径：$(1,1)\to(1,2)\to(2,2)\to(2,3)$。因此该布置仍然是**好的**，所以 $(2,1)$ 位置被放置一个家具，输出 1。 第三次操作尝试在 $(1,2)$ 处放置，因为上一次已经在 $(2,1)$ 放置了一个家具，此时 $(1,1)$ 无法到达 $(n,m)$，因此输出 0，不进行任何修改。 #### 样例解释 2 第一次操作尝试在 $(1,2)$ 处放置，此时这个布置不是**好的**。注意这条路径 $(1,1)\to (2,1)\to (2,2)\to (2,3)\to(1,3)\to(1,4)\to(1,5)\to(2,5)$ 不是一条合法路径，因为不满足只向右向下走的条件。因此输出 0，不进行任何修改。 第一次操作尝试在 $(2,2)$ 处放置，此时存在一条合法路径 $(1,1)\to (1,2)\to(1,3)\to(1,4)\to(1,5)\to(2,5)$。因此该布置仍然是**好的**，所以 $(2,2)$ 位置被放置一个家具，输出 1。 #### 数据规模与约定 #### 本题采用捆绑测试。 - Subtask 1 （5 pts）：$n\le 100,m\le 100$； - Subtask 2 （95 pts）：无特殊限制。 对于 $100\%$ 的数据： - $n\le 1000,m\le 1000$； - $C_{i,j}\in \{0,1\}\ (1\le i\le n,1\le j\le m)$； - $C_{1,1}=C_{n,m}=0$； - 初始布置是**好的**； - $1\le Q\le n\times m$； - $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), C_{X_k,Y_k}\neq 1\ (1\le k\le Q)$； - $(X_k,Y_k)\neq (X_l,Y_l)\ (1\le k