Skip to content

1093: 排方阵

题目

题目描述

ACM班的同学们在yyu的带领下排成了一个N×M的方阵。显然,大家的身高不一定相同。现在,yyu想从中找出一个a×a的正方形区域,使得该区域所有学生中的最高身高和最低身高的差最小。

由于yyu日理万机,所以他想让机智的你帮他解决这个问题。

输入格式

第一行3个整数,分别表示N,M,a的值。

第二行至第N+1行每行M个非负整数,表示方阵中相应位置上同学的身高hij。

输出格式

一行一个整数,表示方阵中所有a*a正方形区域中的最大身高和最小身高之差的最小值。

样例输入

5 4 2

171 172 175 176

170 187 186 170

186 187 172 171

172 180 172 171

171 172 172 172

样例输出

1

数据范围

对于30%的数据,N,M≤100

对于100%的数据,N,M≤1000,0≤hij≤10^9

时间限制:2s

空间限制:512MB

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!