3.泳池小C在一个排水系统不太好的学校上学。又是一个下雨天，学校里高低不平积了很多水。小C突发

3.泳池
小C在一个排水系统不太好的学校上学。又是一个下雨天，学校里高低不平积了很多水。小C突发奇想：如果大雨一直下，多久以后我可以在学校里游泳呢？
学校是 N x N 的坐标方格 grid 中，每一个方格的值 grid(i,j)表示在位置 (i,j) 的高度。现在开始下雨了。当时间为 t 时，此时雨水导致方格中任意位置的水位为 t 。你可以从一个方格游向四周相邻的任意一个方格，但是前提是此时水位必须同时淹没这两个方格。假定小C的游动是不耗时的。
现在小C从坐标方格的左上(0,0)出发。最少耗时多久他才能到达坐标方格的右下平台 (N-1, N-1)？
时间限制：1000
内存限制：65536
输入
第一行有一个整数N，以下是一个N*N的方阵，代表各处的高度。输入范围： 2 ≤ N ≤ 300 0 ≤ Height ≤ 10000000
输出
输出一个整数，代表最少等待时间T
样例输入
样例输入1：
2
0 2
1 3
样例输入2：
5
0 1 2 3 4
24 23 22 21 5
12 13 14 15 16
11 17 18 19 20
10 9 8 7 6
样例输出
样例输出1：
3
样例输出2：
16
提示
样例1：时间为3时，才可以游向平台(1,1)，此时水位为3。样例2：时间为16时，水位为16，此时才能保证(0,0)和(4,4)是联通的（请自行找出一条通路）。

解析：

【喵呜刷题小喵解析】：本题是一道典型的广度优先搜索（BFS）问题，可以使用队列来实现。首先，我们定义一个队列 `queue`，初始时只有起点 `(0, 0, 0)`，其中 `(x, y, time)` 表示当前的位置和对应的时间。然后，我们定义一个集合 `visited`，用于记录已经访问过的位置。接着，我们定义四个方向 `(0, 1), (0, -1), (1, 0), (-1, 0)`，分别表示右、左、下、上。在每一次循环中，我们取出队列中的第一个元素 `(x, y, time)`，如果 `(x, y)` 是终点 `(N-1, N-1)`，则直接返回时间 `time`。否则，我们遍历四个方向，对于每一个方向，计算出下一个位置 `(nx, ny)`，如果 `(nx, ny)` 在网格范围内且没有被访问过，则判断当前位置的水位是否小于等于时间 `time`，如果是，则将 `(nx, ny, time)` 加入队列，并将 `(nx, ny)` 加入 `visited` 集合。如果不是，则直接跳出当前方向的遍历。如果无法到达右下角，则返回 -1。时间复杂度为 O(N^2)，空间复杂度为 O(N^2)。

答案：

解析：

最热门资讯

JAVA工程师面试指导--猎头内部资料

常见面试问题100问！