简答题
偏难
#7157
泳池 学校是 N x N 的坐标方格 grid 中,每一个方格的值 grid(i,j)表示在位置 (i,j) 的高度。现在开始下雨了。当时间为 t 时,此时雨水…
泳池
学校是 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)是联通的(请自行找出一条通路)。
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
int maze[305][305];
bool reach[305][305];
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
int N;
struct point {
int x, y;
point(int a, int b) : x(a), y(b) {}
};
bool canreach(int t) {
if (maze[0][0] > t)
return false;
memset(reach, 0, sizeof(reach));
reach[0][0] = 1;
queue<point> myqueues;
myqueues.push(point(0, 0));
while (!myqueues.empty()) {
point top = myqueues.front();
myqueues.pop();
if (top.x == N - 1 && top.y == N - 1)
return true;
for (int i = 0; i < 4; i++) {
int tx = top.x + dx[i];
int ty = top.y + dy[i];
if (tx < 0 || tx >= N || ty < 0 || ty >= N)
continue;
if (reach[tx][ty])
continue;
if (maze[tx][ty] > t)
continue;
reach[tx][ty] = 1;
myqueues.push(point(tx, ty));
}
}
return false;
}
int main() {
memset(maze, 0, sizeof(maze));
cin >> N;
int L = 10000000, R = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cin >> maze[i][j];
L = min(maze[i][j], L);
R = max(maze[i][j], R);
}
}
int result = 10000000;
while (L <= R) {
int mid = (L + R) / 2;
if (canreach(mid)) {
R = mid - 1;
result = min(result, mid);
} else
L = mid + 1;
}
cout << result << endl;
return 0;
}</pre>
这道题暂未补解析。