题目描述

你正在评估一些关于一个巨型飞机仓库的建设计划。飞机仓库的地面可以表示为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。

输入输出样例

输入样例#1: 复制

输出样例#1: 复制

相当于每次询问两个点之间的最大瓶颈在哪里

也就是转化为求  两条路最小值最大是多少

首先从所有的#开始bfs 求出所有的点距离最近的#是多少

然后贪心的从大到小开始连接 并且钦定 值小的是父节点

注意连边的时候用并查集处理 emm每次需要找到联通块的头 否则可能就不是生成树了

这样的话类似生成树我们可以知道 每次询问的两个点 之间lca上的值即可

 


elijahqi

辣鸡蒟蒻一枚qwq 欢迎加qq qwq 2922945330

发表评论