A46345. 泳池小C在一个排水系统不太好的学校上学。又是一个下雨天，学校里高低不平积了很多水。小C突发奇想：如果大雨一直下，多久以后我可以在学校里游泳呢？学校是 N x N 的坐标方格 grid 中，每一个方格的值 grid(i,j)表示在位置 (i,j) 的高度。现在开始下雨了。当时间为 t 时，此时雨水导致方格中任意位置的水位为 t 。你可以从一个方格游向四周相邻的任意一个方格，但是前提是此时水位必须同…
填空题
困难
知识点
题目描述
泳池
小C在一个排水系统不太好的学校上学。又是一个下雨天，学校里高低不平积了很多水。小C突发奇想：如果大雨一直下，多久以后我可以在学校里游泳呢？
学校是 N x N 的坐标方格 grid 中，每一个方格的值 grid(i,j)表示在位置 (i,j) 的高度。现在开始下雨了。当时间为 t 时，此时雨水导致方格中任意位置的水位为 t 。你可以从一个方格游向四周相邻的任意一个方格，但是前提是此时水位必须同时淹没这两个方格。假定小C的游动是不耗时的。
现在小C从坐标方格的左上(0,0)出发。最少耗时多久他才能到达坐标方格的右下平台 (N-1, N-1)？
输入
第一行有一个整数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)是联通的（请自行找出一条通路）。
参考答案
class Solution {
public:
int swimInWater(vector<vector<int>>& grid) {
int N = grid[0].size();
//标记矩阵
int reached[N][N];
//二分上下界
int min_time = grid[0][0]-1;//不可到达的时间点
int max_time = N*N-1;//可到达的时间点
//广搜数据结构
queue<int> row;
queue<int> col;
int cur_row;
int cur_col;
int time;
while( max_time - min_time > 1 ) {
//二分搜索时间点
time = (max_time + min_time)/2;
//初始化
for( int i = 0; i < N; i++ ) {
for( int j = 0; j < N; j++ ) {
reached[i][j] = 0;
}
}
reached[0][0] = 1;
row.push(0);
col.push(0);
//以当前时间点进行广搜
while( !row.empty() ) {
cur_row = row.front();
cur_col = col.front();
row.pop();
col.pop();
if( cur_row > 0 && grid[cur_row-1][cur_col] <= time && reached[cur_row-1][cur_col] == 0 ) {
reached[cur_row-1][cur_col] = 1;
row.push(cur_row-1);
col.push(cur_col);
}
if( cur_row < N-1 && grid[cur_row+1][cur_col] <= time && reached[cur_row+1][cur_col] == 0 ) {
reached[cur_row+1][cur_col] = 1;
row.push(cur_row+1);
col.push(cur_col);
}
if( cur_col > 0 && grid[cur_row][cur_col-1] <= time && reached[cur_row][cur_col-1] == 0 ) {
reached[cur_row][cur_col-1] = 1;
row.push(cur_row);
col.push(cur_col-1);
}
if( cur_col < N-1 && grid[cur_row][cur_col+1] <= time && reached[cur_row][cur_col+1] == 0 ) {
reached[cur_row][cur_col+1] = 1;
row.push(cur_row);
col.push(cur_col+1);
}
//到达终点可以提前退出
if( reached[N-1][N-1] > 0 ) {
while( !row.empty() ) {
row.pop();
col.pop();
}
}
}
//如果能通过则下调上界
if( reached[N-1][N-1] > 0 ) max_time = time;
//否则上调下界
else min_time = time;
}
return max_time;
}
};
上一题
下一题