← 返回题目
题库练习 Animals and Puzzle
← 上一题 下一题 →

A6890 | Animals and Puzzle

时间限制5s
内存限制512MB
通过 / 提交0/0

题目描述

猫头鹰 Sonya 将一个 $n\times m$ 的湖拼图给刺猬 Filya，当做他的生日礼物。小伙伴们当即去组装这个拼图，然而有一些部分是空的——在那上面没有图片。

令有图片部分的贡献为 $1$，没有的为 $0$。对这个拼图编号，行号从上到下为 $1\sim n$ ，列号从左到右为 $1\sim m$$(1 \le n, m \le 1000) 。$

动物决定继续完成这个拼图，因为它可能更有趣。猫头鹰和刺猬会做出几组询问，每次给出四个整数 $x_1,y_1,x_2,y_2$ ，询问以 $(x_1,y_1)$ 为左上角，$(x_2,y_2)$ 为右下角的区域内，全为 $1$ 的最大正方形的边长。

输入格式

第一行包含两个整数 $n,m$。

接下来 $n$ 行，每行 $m$ 个为 $0$ 或 $1$ 的整数，$1$ 表示有图片，$0$ 表示没有图片。

再一行一个整数 $t$ ，表示 $t$ 组询问。$(1 \le t \le 1000000)$

最后$t$ 行，每行四个整数分别表示 $x_1,y_1,x_2,y_2$。

输出格式

共 $t$ 行，每行 $1$ 个整数，表示区域内最长大的全 $1$ 正方形的边长。

输入输出样例

输入 #1
3 4
1 1 0 1
0 1 1 0
0 1 1 0
5
1 1 2 3
2 1 3 2
3 2 3 4
1 1 3 4
1 2 3 4
输出 #1
1
1
1
2
2
C++ 编辑器
输入
输出