地质学家熊老师

地质学家熊老师

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

熊老师其实还是一名地质学家,他很爱学习地理知识,也很爱到处跑,到处去考察各地风俗民情。

有一天他来到了一个无人小岛,正当熊老师开开心心的准备在沙滩晒太阳的时候,天有不测风云,顿时天空乌云密布、电闪雷鸣!!!海水开始上涨!!!小岛要被海水淹没了!!!

不过好在熊老师朋友众多,他从他的好朋友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)。

提高班测试

未参加
状态
已结束
规则
ACM/ICPC
题目
5
开始于
2018-06-30 08:45
结束于
2018-07-18 06:45
持续时间
430.0 小时
主持人
参赛人数
15