额外提供 $60\%$ 的时间。
小 K 在游玩一款关于迷宫的游戏。
这个迷宫可被看成一个 $n$ 行 $m$ 列的方格图。其中，$a[i][j]=0$ 表示第 $i$ 行第 $j$ 列的方格是通道的一部分，可以行走；$a[i][j]=1$ 则表示该方格是墙壁，不能行走。
游戏会进行若干个回合。对于每一个回合，小 K 会被随机传送到一个位置，同时游戏会生成一颗宝石，同样地随机放到一个位置。这两个位置都不会是墙壁。
小 K 可以向上、下、左、右其中一个方向走，他有无限的时间行走。
对于每个回合，小 K 希望知道，他是否可能到达宝石的位置并获得它。于是，他会询问你 $q$ 次，对于第 $i$ 次询问：
- 他被传送到第 $x_1[i]$ 行第 $y_1 [i]$ 列的位置中。
- 宝石被放到第 $x_2 [i]$ 行第 $y_2 [i]$ 列的位置中。
- 如果经过一定的时间后，他能到达宝石的位置，你需要回答「可以到达」。
- 如果他永远拿不到宝石，你需要回答「无法到达」。
你希望知道你需要回答多少次「可以到达」。
从标准输入 (stdin) 读入数据。
输入的第一行包含一个整数 $c$，表示测试点编号。$c=0$ 表示该测试点为样例。
第二行包含三个正整数 $n,m,q$，以空格分隔。
接下来 $n$ 行，第 $i$ 行包含 $m$ 个非负整数 $a[i][1],a[i][2],a[i][3],…,a[i][m]$，没有任何符号分隔。
接下来 $q$ 行，第 $i$ 行表示第 $i$ 次询问：
- 包含四个正整数 $x_1 [i],y_1 [i],x_2 [i],y_2 [i]$，以空格分隔。
输出到标准输出 (stdout) 中。
输出一行，一个整数表示你需要回答「可以到达」的次数。
0 5 6 2 011001 000100 010000 111010 001010 1 1 5 6 3 3 5 2
1
不公開 測資點#0 (4%): 3.2s , <1M
不公開 測資點#1 (4%): 3.2s , <1M
不公開 測資點#2 (4%): 3.2s , <1M
不公開 測資點#3 (4%): 3.2s , <1M
不公開 測資點#4 (4%): 3.2s , <1M
不公開 測資點#5 (4%): 3.2s , <1M
不公開 測資點#6 (4%): 3.2s , <1M
不公開 測資點#7 (4%): 3.2s , <1M
不公開 測資點#8 (4%): 3.2s , <1M
不公開 測資點#9 (4%): 3.2s , <1M
不公開 測資點#10 (4%): 3.2s , <50M
不公開 測資點#11 (4%): 3.2s , <50M
不公開 測資點#12 (4%): 3.2s , <50M
不公開 測資點#13 (4%): 3.2s , <50M
不公開 測資點#14 (4%): 3.2s , <50M
不公開 測資點#15 (4%): 3.2s , <50M
不公開 測資點#16 (4%): 3.2s , <50M
不公開 測資點#17 (4%): 3.2s , <50M
不公開 測資點#18 (4%): 3.2s , <50M
不公開 測資點#19 (4%): 3.2s , <50M
不公開 測資點#20 (4%): 3.2s , <50M
不公開 測資點#21 (4%): 3.2s , <50M
不公開 測資點#22 (4%): 3.2s , <50M
不公開 測資點#23 (4%): 3.2s , <50M
不公開 測資點#24 (4%): 3.2s , <50M
对于第一次询问，由小 K 的位置走到宝石的位置的路线如下图所示，其中浅灰色的格子是通道，而深灰色的格子是墙壁。因此，你需要回答「可以到达」。
对于第二次询问，可以证明小 K 无论如何行走也无法抵达宝石的位置。因此，你需要回答「无法到达」。
综上，需要回答「可以到达」的次数为 $1$。
数据范围：
- $n,m≤2000$
- $q\le 10^6$
- 对于所有满足 $1≤i≤n,1≤j≤m$ 的整数 $i,j$，$a[i][j]≤1$。
- 对于所有满足 $1≤i≤q$ 的整数 $i$，$x_1 [i],x_2 [i]≤n,y_1 [i],y_2 [i]≤m$。
- 对于所有满足 $1≤i≤q$ 的整数 $i$，$a[x_1 [i]][y_1 [i]]=a[x_2 [i]][y_2 [i]]=0$。
测试点 $1,2$ 满足：$n,m\le 100, q\le 100, \min\{n,m\}=1$。
测试点 $3$~$5$ 满足：$n,m\le 100, q\le 100, \min\{n,m\}=2$。
测试点 $6$~$10$ 满足：$n,m\le 100, q\le 100$。
测试点 $11$~$13$ 满足：$n,m\le 1000, \min\{n,m\}=1$。
测试点 $14$~$16$ 满足：$n,m\le 1000, \min\{n,m\}=2$。
测试点 $17$~$20$ 满足：$n,m\le 1000$。
测试点 $21$~$25$ 没有额外的约束条件。
| ID | User | Problem | Subject | Hit | Post Date |
沒有發現任何「解題報告」 |
|||||