8793: BZOJ4793：[CERC2016]Hangar Hurdles

你正在评估一些关于一个巨型飞机仓库的建设计划。飞机仓库的地面可以表示为n行n列的网格图，其中每个格子要 么是空的，要么有障碍物。行从上到下依次被编号为1到n，列从左到右依次被编号为1到n。存放飞机零件的大型集 装箱能在飞机仓库的地面上自由移动是很重要的。我们可以将每个集装箱看作一个以某个格子为中心的边平行于坐 标轴的正方形。对于一个奇数k，一个尺寸为k的集装箱是一个包含k行k列的正方形。一个集装箱的坐标为其中心格 子的坐标。集装箱可以向上下左右移动，但不能碰到障碍物，且不能移出仓库的边界。给定q对格子A_k和B_k，对 于每对格子，请找到能从A_k移动到B_k的集装箱的最大尺寸，注意这个尺寸也要是一个奇数。

输入格式

第一行包含一个正整数n(2<=n<=1000)，表示仓库的尺寸。 接下来n行，每行n个字符，描述整个仓库，其中“.”表示空格子，“#”表示障碍物。 接下来一行包含一个正整数q(1<=q<=300000)，表示询问的个数。 接下来q行，每行4个正整数r_A,c_A,r_B,c_B(1<=r_A,c_A,r_B,c_B<=n)，分别表示A和B的坐标。 输入数据保证A和B是不同的空格子。

输出格式

输出q行，每行一个整数，对于每个询问输出最大尺寸，如果不存在解，那么输出0。

样例输入

7
.....#.
...#.#.
....#..
....###
....#..
#......
.......
5
2 5 5 2
2 5 3 6
2 2 6 3
2 2 6 6
1 1 7 7

样例输出

1
0
3
1
1

提示

没有写明提示

题目来源

没有写明来源