首页 › 题库 › C/C++编程考级 › C/C++编程五级 › 简答题
简答题 偏难
#7385

泳池 小C在一个排水系统不太好的学校上学。又是一个下雨天,学校里高低不平积了很多水。小C突发奇想:如果大雨一直下,多久以后我可以在学校里游泳呢? 学校是 N x…

泳池

小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)是联通的(请自行找出一条通路)。

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">//动规+广搜+二分 //从(0,0)到(N-1,N-1)的各条路径最大值中的最小值。 //直接深搜和广搜会超时   #include &lt;bits/stdc++.h&gt; using namespace std; int n,m[305][305];// n 是矩阵的大小,m 存储矩阵元素 bool v[305][305];// v 记录矩阵中点是否被访问过 int dx[4]={-1,1,0,0}; int dy[4]={0,0,-1,1}; struct Point{ int x,y; Point(int a,int b):x(a),y(b){} }; bool is_reach(int t){// 判断是否在时间t内到达右下角坐标 if(m[0][0]&gt;t) return false;// 左上角大于t无法到达 memset(v,0,sizeof(v)); v[0][0]=1; queue&lt;Point&gt; myq;// 创建一个队列存储待访问的点 myq.push(Point(0,0)); while(!myq.empty()){ Point top=myq.front(); myq.pop(); // 到达右下角坐标,返回true if((top.x==n-1)&amp;&amp;(top.y==n-1)) return true; for(int i=0;i&lt;4;i++){ int xx=top.x+dx[i]; int yy=top.y+dy[i]; // 如果已访问过或元素大于t,则无法继续前进 if(xx&lt;0||xx&gt;=n||yy&lt;0||yy&gt;=n||v[xx][yy]||(m[xx][yy]&gt;t)) continue; v[xx][yy]=1;// 标记坐标访问状态 myq.push(Point(xx,yy));// 将可继续访问的坐标加入队 } } return false;// 无法到达右下角坐标,返回false } int main() { memset(m,0,sizeof(m)); cin&gt;&gt;n; int L=1e7,R=0; for(int i=0;i&lt;n;i++) for(int j=0;j&lt;n;j++){ cin&gt;&gt;m[i][j]; L=min(L,m[i][j]); R=max(R,m[i][j]); } int result=1e7; while(L&lt;R){// 二分查找 int mid=(L+R+1)/2; if(is_reach(mid)){// mid值能到达右下角坐标 R=mid-1; result=min(result,mid);// 更新结果 } else  L=mid; } cout&lt;&lt;result;     return 0; }</pre>
这道题暂未补解析。