题目背景

迷宫是一个n行m列的网格，其中有一些是空格，可以站人，其中一些是障碍物，不仅不能站人、不能经过，并且这些障碍物有强大的磁力，全身穿着铠甲的勇者，一旦站在障碍物的上、下、左、右相邻的网格，则会被强大的磁力吸住，无法继续移动。勇者只能全程站某一个空格上，并且每次移动只能移动到上、下、左、右相邻的空格网格上。

题目描述

给出n行m列的的迷宫网格信息，另外有q次查询，每次查询均需要求出，勇者从$(h{i1},v{i1})出发，能否移动到(h{i2},v{i2})$。

输入的第一行包含三个数字n,m,q。

接下来n行，每行m个字符，表示迷宫网格，其中字符’.’表示空格，’#’表示障碍物。

接下来q行，每行4个数字$h{i1}、v{i1}、h{i2}、v{i2}$，分别表示勇者的起点行号、起点列号、终点行号、终点列号。

输出仅一行，一个由0和1组成的长度为q的数字串，表示q组查询的结果，0表示不能，1表示能。

样例1解释 

网格如下图所示，其中绿色网格表示受到磁力影响的网格：

对于第一组查询，需要从(2,3)移动到(1,5)。移动路线如下：

对于第二组查询，需要从(1,5)移动到(3,1)，当移动到(2,2)时，会受到磁力影响，无法继续移动。

对于第三组查询，需要从(2,4)移动到(2,2)，虽然终点是受到磁力影响的网格，但是仍然可以移动到。

数据范围

对于所有测试数据有：$1≤n,m,q≤1000,1\leq h{i1},h{i2}\leq n,1\leq v{i1},v{i2}\leq m。保证起点和终点都不是障碍网格。 |测试点| n,m≤| q≤$| 特殊性质| |-----|-----|-----|-----| |1~3| 10| 10| 无| |4~5| 100| 10| 无| |6| 100| 100| A| |7~8| 100| 100| B| |9~10| 100| 100| 无| |11~12| 100| 1000| 无| |13~14| 1000| 10| 无| |15| 1000| 1000| A| |16~17| 1000| 1000| B| |18~20| 1000| 1000| 无|

特殊性质A：地图的第1行、第n行、第1列、第m列的所有网格都是障碍物，其余网格均不为障碍物。

特殊性质B：起点和终点均不与障碍物上、下、左、右相邻。 

2026第五届青少年编程挑战精英赛