2
.
#include<bits/stdc++.h>
using namespace std;
const int dx[4]={1,-1,0,0}, dy[4]={0,0,1,-1}; //①
int n, a[105][105], vis[1050][1050], w, flag;
void dfs(int x, int y, int tmin, int tmax) {
if(flag) return;
if(a[x][y] > tmax || a[x][y] < tmin)
return;
vis[x][y] = true;
if(x == n && y == n) {
flag = true;
return;
}
for(int i=0; i<4; i++) {
int nx = x + dx[i], ny = y + dy[i];
if(!vis[nx][ny] && 1 <= nx && nx <= n && 1 <= ny && ny <= n)
dfs(nx, ny, tmin, tmax);
}
}
bool check(int x) {
for(int i=1; i+x<=w; i++) {
memset(vis, 0, sizeof(vis));
flag = false;
dfs(1, 1, i, i+x);
if(vis[n][n])
return true;
}
return false;
}
int main() {
cin >> n;
for(int i=1; i<=n; i++) {
for(int j=1; j<=n; j++) {
cin >> a[i][j];
w = max(a[i][j], w);
}
}
int l = 1, r = w, ans = 0;
while(l <= r) {
int mid = (l + r) / 2;
if(check(mid)) {
r = mid - 1;
ans = mid;
l = mid + 1;
}
cout << ans << endl;
return 0;
}
假设输入数据满足 1≤n≤100,1≤ai,j≤1000,完成下面的判断题和单选题:
判断题
(1)若读入的 a 均相等,则最后一次调用 check 函数,函数内 for 循环只会被执行 a -1次。()
(2)若某组数据满足 w=1000,则 check 函数总是会被调用 10 次。()
(3)若将①处的常量定义改为 const int dx[4]={-1, 0, 0, 1}, dy[4]={0, -1, 1, 0}; 不影响程序运
行结果。()
选择题
4)当输入的数据满足 w=1,则算法的时间复杂度为()
A. O(n2) B. O(n2logn) C. O(n2log2n)D. O(n3logn)
5)当输入的数据满足所有的=1000,则算法的时间复杂度为()
A. O(n2) B. O(n2w) C. O((n2+w)logw)D. O(n2wlog2w)
6)当输入为下列数据,则输出为多少()
5
1 6 3 8 9
2 3 5 12 8
7 9 4 7 2
11 4 5 4 10
2 5 9 1 3
A. 4
B. 5
C. 11
D. 14