baingbaboom正在往北边跑!!!
现在在一张N*M的地图上有K只babingbaboom!!!对于一张地图上的点都有一个 h_{i,j} 来表示这个地方的高度。现在这些babingbaboom都想要跑到北边的一个山坡上。求出离每一个babingbaboom最近的靠北的山。
补充定义:
山:
山的周围没有比它更高的地方。(四联通)
在北边:
令Babingbaboom的坐标为 A(a,b) ,山的坐标为 B(x,y) ,山在Babingbaboom的北边当且仅当 dis_{A,B}==a-x
切比雪夫距离:
A(x_1,y_1) 和 B(x_2,y_2) 两点之间的切比雪夫距离: dis_{A,B}=max(|x_1 - x_2|, |y_1 - y_2|) 和 两 点 之 间 的 切 比 雪 夫 距 离
第1行三个正整数N,M,K。
第2-N+1行每行有M个正整数 h_{i,j} 。
第N+2-N+K+1行每行有两个正整数X_i,Y_i表示每一个babingbaboom的坐标。
K行。如果对于每一个babingbaboom存在这样的最近的山(切比雪夫距离),就输出这个babingbaboom到山的切比雪夫距离;否则输出“Pool Babingbaboom!”(不要引号!(我知道可怜的是Poor,但是我就爱写Pool))
5 5 5 1 2 3 4 5 2 3 4 5 1 3 4 5 1 2 4 5 1 2 3 5 1 2 3 4 1 2 2 3 3 4 4 5 5 1
Pool Babingbaboom! Pool Babingbaboom! 1 2 0
1 \leqslant N,M \leqslant 1e3
1 \leqslant K \leqslant 1e5
1 \leqslant h_{i,j} \leqslant 1e9
数据有梯度!
样例图片(星代表一个Babingbaboom,红色代表一个山): (竖的是x,横的是y。画的时候没注意,很抱歉。)