c++阅读程序求解答

Question

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

Answer 1

判断题

（1）若读入的 a 均相等，则最后一次调用 check 函数，函数内 for 循环只会被执行 a-1 次。（错）

• 解析：若 a 数组中的所有元素相等，意味着整个矩阵中的所有值都相等，无论 check 函数中 for 循环的上下界是多少，dfs 都会从起点走到终点。因此，for 循环会遍历整个区间，而不仅仅是 a-1 次。

（2）若某组数据满足 w=1000，则 check 函数总是会被调用 10 次。（错）

• 解析：w 是 a 数组中最大的元素值，check 函数的调用次数取决于二分查找的中值范围。在最坏情况下，当 w=1000 时，二分查找的次数为 log2(1000)，也就是大约 10 次。因此，check 函数可能会被调用 10 次，但这不是必然的。

（3）若将①处的常量定义改为 const int dx[4]={-1, 0, 0, 1}, dy[4]={0, -1, 1, 0}; 不影响程序运行结果。（对）

• 解析：这里的 dx 和 dy 定义的是移动方向的顺序。虽然顺序改变了，但依旧涵盖了所有可能的上下左右方向，因此不会影响程序的运行结果。

选择题

4）当输入的数据满足 w=1，则算法的时间复杂度为（**A. O(n^2)**）

• 解析：当 w=1 时，意味着所有元素都相等，二分查找只会执行一次，所以复杂度是 O(n^2)。

5）当输入的数据满足所有的 a[i][j]=1000，则算法的时间复杂度为（**D. O(n^2 w log^2 w)**）

• 解析：在最坏情况下，w 等于 1000，二分查找会在 log2(w) 次内完成，每次查找都要遍历整个矩阵，因此时间复杂度为 O(n^2 w log^2 w)。

6）当输入为下列数据，则输出为多少（B. 5）

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

• 解析：对于这个具体的输入矩阵，通过模拟算法执行，可以得到最后输出的最小差值为 5。