1007. 用传送门来让网格连通吧

题目描述

给定一个 $n\times m$ 的网格，每个格子为以下两种类型之一：

• .：可以通行；
• #：障碍物，不能进入。

从一个可通行格子出发，每次可以移动到与它上、下、左、右相邻的可通行格子。

网格中还有 $k$ 个有向传送门。每个传送门包含一个入口和一个出口。当到达入口格子时，可以选择立即传送到对应的出口格子，也可以不使用传送门。一个格子上可以存在多个传送门。

共有 $q$ 次询问。每次给定一个起点和一个终点，判断能否从起点到达终点。

输入格式

第一行输入一个整数 $T$，表示测试数据组数。

每组测试数据的格式如下：

第一行输入四个整数 $n,m,k,q$，分别表示网格行数、列数、传送门数量和询问数量。

接下来 $n$ 行，每行输入一个长度为 $m$ 的字符串，描述网格。字符 . 表示可以通行，字符 # 表示障碍物。

接下来 $k$ 行，每行输入四个整数 $x_1,y_1,x_2,y_2$，表示一个从 $(x_1,y_1)$ 指向 $(x_2,y_2)$ 的传送门。

接下来 $q$ 行，每行输入四个整数 $x_1,y_1,x_2,y_2$，表示询问能否从 $(x_1,y_1)$ 到达 $(x_2,y_2)$。

对于一组测试数据：

$1\le n,m$；

$1\le n\cdot m\le 5\times 10^4$；

$0\le k\le 100$；

$1\le q\le 10^5$；

$1\le x_1,x_2\le n$；

$1\le y_1,y_2\le m$。

输入保证所有传送门的入口、出口以及询问的起点、终点均不是障碍物。

OJ 中只有一个正式测试点，该测试点满足：

$T=400$；

$\sum n\cdot m=10^7$；

$\sum k=40000$；

$\sum q=10^7$。

输出格式

对于每次询问输出一行：

• 如果能从起点到达终点，输出 1；
• 否则输出 0。

样例输入

3
4 3 2 1
.#.
##.
#..
...
1 1 1 3
4 1 4 2
4 1 3 2
3 3 1 3
.#.
###
.#.
1 1 3 1
1 1 3 1
3 1 1 1
1 3 3 3
1 5 2 3
.#.#.
1 1 1 3
1 3 1 5
1 1 1 5
1 5 1 1
1 3 1 3

样例输出

1
1
0
0
1
0
1

提示

数据量较大，推荐使用快读，或者关同步的cin读入。

来源：2026杭电多校-测试专用（肖岱恩） 原题链接：http://acm.hdu.edu.cn/contest/problem_show.php?cid=1236&pid=1007