问题 H: 烟花易逝
时间限制: 1 Sec 内存限制: 128 MB
题目描述
烟花在天空中留下的光点消失之后，会变成雨，会变成雪，重新落到地上。它们滋润了大地，抚育了人类，为的是再一次被送上天空，重现华丽的瞬间。
12月25日，也许对你来说是个挺重要的日子，受友人所托，或是为了弥补心中的遗憾，你早早地来到了这里。白天繁华的一切都随着夜幕的降临沉淀出些许难得的安静，漫无目的的人群匆匆经过，只能听见偶尔疾驶而过的汽笛声。
已经快到约定的时间了，远方隐约可以看见二人并肩的影子，你点燃了手中的引线。随着几声轻响，一群逆飞的流星带着所有的祝福，穿过了厚重的云层，划破了黑寂的夜空。在最高空绽放、四散而出的烟花在夜空中不断闪烁，宛如在漆黑的幕布上挥洒下华丽的翡翠流苏，天空万紫千红，千姿百态的繁花让人眼花缭乱。天空下所有忙碌的人们都不约而同停下了脚步，向着遥远的天边望去，不知这绚烂的烟花，让他们回忆起了什么呢？正是因为有大家的寄托，烟花才能以如此美妙的姿态一直存在下去吧。
上一次看到这样的烟花是什么时候呢，连当年的人、当年的事都已经记不清了，只是看着这漫天的烟花时，心中涌出一丝莫名的孤独，如在高空中同真实的鲜花一般绽放消散的记忆。一瞬的璀璨过后，转眼间，天空中只剩下烟云般花团和花瓣的痕迹，随风缓缓地飘向远方。烟花还是结束了，在完成了它的使命之后，变成灰尘流落于世间。“夏夜空出现在遥远的的记忆，绽放的璀璨花火拥着繁星”，若当时像他那样勇敢，也许今日便不会如此吧。
“又是一个人在这里看烟花吗？”熟悉的声音从耳边传来，“明年我们一起看吧。”最美的烟花配最棒的瞬间，那些易逝的小心情就这么被封装在烟花里，以另一种形式传承下去。
她非常喜欢烟花，于是拍下了一张烟花的照片，想问你在这张照片里以某一点(a,b)为中心的烟花最大可能的半径是多少？
半径为R的烟花定义是：所有与中心点的距离小于等于R的点都必须在照片内，对于这些点，将其与在照片内的所有的相邻点比较，离中心点较近的点亮度较大。即当两个在照片中的点(xi,yi),(xj,yj)满足|xi-a|+|yi-b|<=R&&|xj-a|+|yj-b|<=R时，如果|xi-a|+|yi-b|<|xj-a|+|yj-b|且|xi-xj|+|yi-yj|==1，则light(xi,yi)>light(xj,yj)。
输入
第一行包含两个整数n(n<=100)，q(q<=20)代表照片的大小与询问的次数，接着有一个n行n列的矩阵，描述了这张照片的亮度light(light(i,j)<=100)，最后q行，每行有2个数字a,b，代表每个询问中烟花的中心点。
输出
输出有q行，每行一个整数，代表对于中心点为(a,b)的烟花最大半径R。
样例输入
6 3
3 2 1 2 1 2
2 1 1 1 2 1
1 1 2 1 3 2
1 2 3 2 1 1
3 1 2 1 1 0
2 1 1 0 0 0
3 5
4 3
1 6
样例输出
1
2
0
思路
由于 n <= 100 , q <= 20 我们可以模拟
① 我们可以令从R = 0 开始模拟
② 先找到与(a , b) 距离 R+1 的点 ，检测这个点是否比与(a , b)距离 R 的点小 ， 然后计数
③ 再检测数量，因为当R = 0 时 可能有四个 ，当 R = 1 时 可能有12个(重复计数了4个) ，依此类推，检测数量是否等于 4*(2*R+1) 即可 再使R自增 后再进入循环，否则 输出 R
#include <bits/stdc++.h>using namespace std;
int X,Y,n;
int flag[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
bool awa () {if (X > 0 && X <= n && Y > 0 && Y <= n) {return true ;}return false ;
}
int main(){int a,b,R,q,cnt,L[101][101];cin >> n >> q ;for (int i = 1 ; i <= n ; i++) {for (int j = 1 ; j <= n ; j++) {cin >> L[i][j] ;}}for (int i = 0 ; i < q ; i++) {cin >> a >> b ;R = cnt = 0 ;if (a == 1 || a == n || b == 1 || b == n) {} else {while (1) {for (int j = 1 ; j <= n ; j++) {for (int k = 1 ; k <= n ; k++) {if (abs(j-a) + abs(k-b) == R + 1) {//printf("|L[%d][%d]距离为R+1\n",j,k);for (int l = 0 ; l < 4 ; l++) {X = j + flag[l][0] ;Y = k + flag[l][1] ;if (awa()) {if (abs(X-a) + abs(Y-b) == R) {if (L[j][k] < L[X][Y]) {//printf("L[%d][%d] < L[%d][%d]\n",j,k,X,Y);cnt++ ;}}}}}}}//printf("cnt = %d\n",cnt);if (R == 0) {if (cnt == 4*(R+1)) {cnt = 0 ;R++ ;} else {break ;}} else {if (cnt == 4*(2*R+1)) {cnt = 0 ;R++ ;} else {break ;}}}}cout << R << endl ;}return 0;
}
/**************************************************************Problem: 2292User: 21XXXXXXXXLanguage: C++Result: 正确Time:11 msMemory:2024 kb
****************************************************************/
