地质学家熊老师
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
题目描述
熊老师其实还是一名地质学家,他很爱学习地理知识,也很爱到处跑,到处去考察各地风俗民情。
有一天他来到了一个无人小岛,正当熊老师开开心心的准备在沙滩晒太阳的时候,天有不测风云,顿时天空乌云密布、电闪雷鸣!!!海水开始上涨!!!小岛要被海水淹没了!!!
不过好在熊老师朋友众多,他从他的好朋友Tony老师那了解到,海水不会一直上涨,一定只会涨k分钟。而且熊老师在上岛前做足了功课,他把整个岛分成了一个含有n*n个格子的正方形,每个格子A[i][j]都有它自己的海拔高度h。现已知海平面的海拔为0,每分钟上涨1个海拔高度,请你求出k分钟后,原来的大岛将被海水分成多少个小岛(即安全区域),以及他从他现在所在的位置sx,sy(第sx行、sy列,从0开始),到任意一个安全区域的最短距离(假设熊老师走得非常快,移动不需要时间)。
为了让他以后还能再教你们信息奥赛,请你们帮帮他,带他逃离这个困境。
格式
输入格式
第一行有4个整数n, k, sx, sy。(0 < n, sx, sy <= 40, 0 <= k <= 10^8),
接下来n行,每行n个整数h(0 <= h <= 10^8),代表每个格子A[i][j]的海拔高度h
输出格式
若k分钟后还有小岛,则在一行内输出两个整数,用空格隔开,分别代表原来的大岛将被海水分成小岛的个数(即安全区域的个数)、熊老师从他所在的位置到任意一个安全区域的最短距离。
若k分钟后没有小岛,则在一行内输出"Teacher Xiong, we will miss you!"。
样例
样例输入1
5 4 4 0
1 2 3 4 5
1 2 3 4 4
1 2 3 3 3
1 2 2 2 2
1 1 1 1 1
样例输出1
1 8
样例输入2
5 3 2 0
1 2 3 4 5
2 0 3 4 4
3 3 0 3 3
4 4 3 0 2
5 4 3 2 1
样例输出2
2 1
限制
1s, 1024KiB for each test case.
Hint
样例1表示,4分钟后,原来的大岛被海水分成了一个小岛,只剩下了(0, 4)这一个小格子,因此熊老师从(4, 0)这个位置走到(0, 4)的最短路径为8。
样例2表示,3分钟后,原来的大岛被海水分成了两个小岛,只剩下了{(0,4),(0,3),(1,3),(1,4)}和{(4,0),(3,0),(3,1),(4,1)}这两个小岛,熊老师从(2,0)这个点走到任意一个小岛的最短路为1,即从(2,0)走到(3,0)。