首页 › 试卷 › C/C++编程考级 › C/C++编程五级 › 青少年软件编程(C语言五级)等级考试真题试卷(2022年6月)

青少年软件编程(C语言五级)等级考试真题试卷(2022年6月) VIP

C/C++编程五级 共 4 题 2022 年 含标准答案与解析
返回试卷列表
本页为整卷浏览:先自己做一遍,再展开「查看答案与解析」核对。

一、简答题

1. 简答题

逃离迷宫

你在一个地下迷宫中找到了宝藏,但是也触发了迷宫机关,导致迷宫将在T分钟后坍塌,为此你需要在T分钟内逃离迷宫,你想知道你能不能逃离迷宫。迷宫是一个边长为m的正方形,其中"S"表示你所在的位置,"E"表示迷宫出口,"."是可以随意走动的区域,"#"是不可穿行的墙壁,每次你可以耗费1分钟在区域间移动(上下左右四个方向)。

时间限制:1000

内存限制:65536

输入

输入包含多组数组,第一行是一个整数K(1 <= K <= 10),表示有K组数据。接下来每组数组包含整数m(2<=m<=10)和整数T,m表示正方形迷宫的边长,T表示坍塌时间。其后是一个m*m的字符矩阵,包含字符"S", "E", "."和"#"。

输出

每组数据输出一行,输出“YES"或者"NO",表示是否可以在坍塌之前逃离(也就是说移动次数是否可以不超过T)。

样例输入

2
4 7 
S...
###.
.#E.
..#.
3 4
S..
..#
.#E

样例输出

YES
NO
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;stdio.h&gt; #include &lt;stdlib.h&gt; #include &lt;stdbool.h&gt; #include &lt;string.h&gt; #define MAX_M 12   struct node {     int x, y;     int tcnt; };   int m, t; char mat[MAX_M][MAX_M];   int bfs(int x0, int y0, int x1, int y1) {     if (x0 == x1 &amp;&amp; y0 == y1) {         return 0;     }     struct node nd = {x0, y0, 0};     int x, y;     struct node q[MAX_M * MAX_M];     int front = 0, rear = 0;     q[rear++] = nd;     while (front &lt; rear) {         nd = q[front++];         x = nd.x;         y = nd.y;         if (x &lt; m - 1) {             if (mat[x + 1][y] == 'E') {                 return nd.tcnt + 1;             } else if (mat[x + 1][y] == '.') {                 struct node newNode = {x + 1, y, nd.tcnt + 1};                 q[rear++] = newNode;                 mat[x + 1][y] = '*';             }         }         if (x &gt; 0) {             if (mat[x - 1][y] == 'E') {                 return nd.tcnt + 1;             } else if (mat[x - 1][y] == '.') {                 struct node newNode = {x - 1, y, nd.tcnt + 1};                 q[rear++] = newNode;                 mat[x - 1][y] = '*';             }         }         if (y &lt; m - 1) {             if (mat[x][y + 1] == 'E') {                 return nd.tcnt + 1;             } else if (mat[x][y + 1] == '.') {                 struct node newNode = {x, y + 1, nd.tcnt + 1};                 q[rear++] = newNode;                 mat[x][y + 1] = '*';             }         }         if (y &gt; 0) {             if (mat[x][y - 1] == 'E') {                 return nd.tcnt + 1;             } else if (mat[x][y - 1] == '.') {                 struct node newNode = {x, y - 1, nd.tcnt + 1};                 q[rear++] = newNode;                 mat[x][y - 1] = '*';             }         }     }     return -1; }   int main() {     int k, i, j, x0, y0, x1, y1, ans;     scanf("%d", &amp;k);     while (k--) {         scanf("%d %d", &amp;m, &amp;t);         for (i = 0; i &lt; m; i++) {             for (j = 0; j &lt; m; j++) {                 scanf(" %c", &amp;mat[i][j]);                 if (mat[i][j] == 'S') {                     x0 = i;                     y0 = j;                 } else if (mat[i][j] == 'E') {                     x1 = i;                     y1 = j;                 }             }         }         ans = bfs(x0, y0, x1, y1);         if (ans &lt;= t &amp;&amp; ans &gt;= 0) {             printf("YES\n");         } else {             printf("NO\n");         }     }     return 0; }</pre>
这道题暂未补解析。
2. 简答题

夺宝探险

你无意中发现了装满了宝藏的迷宫,你想要获得尽可能多的宝藏,但是迷宫里的机关阻碍了你的计划。迷宫的地面是M行N列的矩形网格,每格是一块带有机关且放置了1个宝藏的地砖,宝藏一共有K种,用1-K表示其种类,迷宫的入口只有一个,为迷宫的第一行第一列。地砖的机关如下:

1. 每次你只能踏到你与你所在地砖相邻的地砖上(即前后左右4块);

2. 当你踏上某块地砖后,其上的宝藏(假设种类为k)自动归属你,同时所有放置了种类为k的宝藏的地砖碎裂,你无法踏上,你当前所在的地砖在你离开后也会立刻碎裂;

3. 当你无路可走的时候,你会被传送回迷宫出口,无法再进入迷宫。

你想知道你最多能获得多少宝藏。

时间限制:1000

内存限制:65536

输入

输入的第一行是三个用空格隔开的整数,分别是M、N和K(1 <= M,N <= 20, 1 <= K <= 100) 之后是M行,每行包含N个范围为1-K的整数,用空格隔开,表示放置的宝藏种类

输出

只有一行,为一个整数,表示最多能获得的宝藏个数。

样例输入

3 4 5
1 2 3 3
2 1 4 3
1 5 1 2

样例输出

4
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;iostream&gt; using namespace std; int m, n, k; int a[22][22]; bool jewel[101]; int have = 0; // 获得的宝石数 int ans = 0; int dirx[4] = {0, 0, 1, -1}; int diry[4] = {1, -1, 0, 0}; void dfs(int x, int y) {   for (int i = 0; i &lt; 4; i++) {     int nx = x + dirx[i];     int ny = y + diry[i];     if (!jewel[a[nx][ny]]) {       jewel[a[nx][ny]] = true;       have++;       dfs(nx, ny);       have--;       jewel[a[nx][ny]] = false;     }   }   ans = max(ans, have); } int main() {   cin &gt;&gt; m &gt;&gt; n &gt;&gt; k;   int i, j;   for (i = 1; i &lt;= m; i++)     for (j = 1; j &lt;= n; j++)       cin &gt;&gt; a[i][j];   jewel[a[1][1]] = true;   jewel[0] = true;   have = 1;   dfs(1, 1);   cout &lt;&lt; ans;   return 0; }</pre>
这道题暂未补解析。
3. 简答题

晶矿的个数

在某个区域发现了一些晶矿,已经探明这些晶矿总共有分为两类,为红晶矿和黑晶矿。现在要统计该区域内红晶矿和黑晶矿的个数。假设可以用二维地图m[][]来描述该区域,若m[i][j]为#表示该地点是非晶矿地点,若m[i][j]为r表示该地点是红晶矿地点,若m[i][j]为b表示该地点是黑晶矿地点。一个晶矿是由相同类型的并且上下左右相通的晶矿点组成。现在给你该区域的地图,求红晶矿和黑晶矿的个数。

时间限制:1000

内存限制:65536

输入

第一行为k,表示有k组测试输入。 每组第一行为n,表示该区域由n*n个地点组成,3 <= n<= 30 接下来n行,每行n个字符,表示该地点的类型。

输出

对每组测试数据输出一行,每行两个数字分别是红晶矿和黑晶矿的个数,一个空格隔开。

样例输入

2
6
r##bb#
###b##
#r##b#
#r##b#
#r####
######
4
####
#rrb
#rr#
##bb

样例输出

2 2
1 2
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;bits/stdc++.h&gt; using namespace std; const int N = 30; char b[N][N + 1]; int n; void dfs(int r, int c, char type) {   if (r &lt; 0 || r &gt;= n || c &lt; 0 || c &gt;= n)     return;   if (b[r][c] != type)     return;   b[r][c] = '#';   dfs(r - 1, c, type);   dfs(r + 1, c, type);   dfs(r, c - 1, type);   dfs(r, c + 1, type); } int main() {   int k;   scanf("%d", &amp;k);   while (k--) {     scanf("%d", &amp;n);     for (int i = 0; i &lt; n; i++)       scanf("%s", b[i]);     int rcnt = 0, bcnt = 0;     for (int i = 0; i &lt; n; i++)       for (int j = 0; j &lt; n; j++)         if (b[i][j] == 'r') {           rcnt++;           dfs(i, j, 'r');         } else if (b[i][j] == 'b') {           bcnt++;           dfs(i, j, 'b');         }     printf("%d %d\n", rcnt, bcnt);   }   return 0; }</pre>
这道题暂未补解析。
4. 简答题

冠军之路

当训练师眼神对上的那一刻,就会开始对战。

lxz来到了冠军之路的山洞中。山洞的地图是一个N*M的矩形。在地图中,'.'代表可以行走的地面,'#'代表无法行走的岩石。'I'代表山洞的入口,即lxz现在所在的位置。'O'表示冠军之路的出口。lxz可以向上下左右四个方向行走。矩形的四周都是山洞的岩石,无法行走。

冠军之路中有一些精英训练师,他们可能面向上、下、左、右四个方向,在地图上用'w','a','s','d'表示,其中'w'表示向上。's'表示向下。'a'表示向左。'd'表示向右(这些位置不可行走)。如果lxz出现在精英训练师正对方向的一条线上,且没有被岩石或其他精英训练师阻挡,那么lxz就会与这个精英训练师进行对战。每位训练师只会与lxz对战一次。

为了通过冠军之路,lxz必须击败所有精英训练师。lxz希望找到一条击败所有精英训练师并走到冠军之路出口的最短路径。

时间限制:1000

内存限制:65536

输入

第一行是两个整数,N, M表示地图的大小。 0 < N, M <= 100 接下来是N行,每行M个字符,代表冠军之路的地图。训练师的个数不超过8

输出

一个整数,表示击败所有精英训练师并走到冠军之路出口的最短路径的长度。如果无法击败所有精英训练师或者无法到达出口,输出-1。

样例输入

3 3
Id.
...
Oa#

样例输出

8
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;algorithm&gt; #include &lt;iostream&gt; #include &lt;limits&gt; #include &lt;queue&gt; #include &lt;vector&gt; using namespace std; /* 3 3 Id. ... Oa# */ struct point {   int x, y;   point(int x, int y) : x(x), y(y) {}   point() : x(0), y(0) {}   bool operator==(const point &amp;p) const { return x == p.x &amp;&amp; y == p.y; }   bool operator&lt;(const point &amp;p) const {     if (x == p.x)       return y &lt; p.y;     return x &lt; p.x;   } }; struct item {   point pt;   char c;   item(point p, char c) {     pt.x = p.x;     pt.y = p.y;     this-&gt;c = c;   } }; int direct[4][2] = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}}; int a[105][105]; char d[105][105]; int pass[105][105]; vector&lt;vector&lt;point&gt;&gt; pts; vector&lt;item&gt; base; point bp, ep; int n, m; int bfs(point from, point to) {   queue&lt;point&gt; q;   char path[105][105] = {0};   q.push(from);   int ans = 0;   while (q.size()) {     // TODO     int size = q.size();     for (int k = 0; k &lt; size; k++) {       point cur = q.front();       q.pop();       path[cur.x][cur.y] = 1;       if (cur == to) {         return ans;       }       for (int i = 0; i &lt; 4; i++) {         point dst;         dst.x = cur.x + direct[i][0];         dst.y = cur.y + direct[i][1];         if (dst.x &gt;= n || dst.x &lt; 0)           continue;         if (dst.y &gt; m || dst.y &lt; 0)           continue;         if (path[dst.x][dst.y] == 0 &amp;&amp;             (d[dst.x][dst.y] == '.' || d[dst.x][dst.y] == 'O' ||              d[dst.x][dst.y] == 'I')) {           q.push(dst);         }       }     }     ans++;   }   return 0; } vector&lt;point&gt; getpoints(char pos, point p) {   vector&lt;point&gt; res;   string ss = ".IO";   if (pos == 'w') {     for (int i = p.x - 1; i &gt;= 0; i--)       if (ss.find(d[i][p.y]) != string::npos)         res.push_back(point(i, p.y));       else         break;   }   if (pos == 's') {     for (int i = p.x + 1; i &lt; m; i++)       if (ss.find(d[i][p.y]) != string::npos)         res.push_back(point(i, p.y));       else         break;   }   if (pos == 'a') {     for (int i = p.y - 1; i &gt;= 0; i--)       if (ss.find(d[p.x][i]) != string::npos)         res.push_back(point(p.x, i));       else         break;   }   if (pos == 'd') {     for (int i = p.y + 1; i &lt; n; i++)       if (ss.find(d[p.x][i]) != string::npos)         res.push_back(point(p.x, i));       else         break;   }   return res; } /* void showpath(int i, int j) {     if (i == j) return;     if (pass[i][j] == 0) {         printf("%d -&gt; %d \n",i , j);         route.push_back(j);     } else {         showpath(i, pass[i][j]);         showpath(pass[i][j], j);     } } */ int getMinBfs(point pt, vector&lt;int&gt; &amp;idx, vector&lt;int&gt; &amp;p,               vector&lt;vector&lt;point&gt;&gt; pts) {   int minval = INT32_MAX;   for (uint32_t i = 0; i &lt; pts.size(); i++) {     for (uint32_t j = 0; j &lt; pts[i].size(); j++) {       int dis = bfs(pt, pts[i][j]);       if (minval &gt; dis) {         minval = dis;         idx.clear(), p.clear();         idx.push_back(i), p.push_back(j);       } else if (minval == dis) {         idx.push_back(i), p.push_back(j);       }     }   }   return minval; } vector&lt;point&gt; getMinPoints(point pt, vector&lt;vector&lt;point&gt;&gt; pts) {   vector&lt;point&gt; res;   int idx, p;   for (uint32_t i = 0; i &lt; pts.size(); i++) {     int minval = INT32_MAX;     for (uint32_t j = 0; j &lt; pts[i].size(); j++) {       int dis = bfs(pt, pts[i][j]);       if (minval &gt; dis) {         minval = dis;         idx = i, p = j;       }     }     res.push_back(pts[idx][p]);   }   return res; } // 贪心法+bfs搜索计算最小路径 int getMinPath(point bp, point ep, vector&lt;vector&lt;point&gt;&gt; points) {   int sum = 0, minSum = INT32_MAX;   vector&lt;int&gt; idx, p;   vector&lt;point&gt; ap;   vector&lt;vector&lt;point&gt;&gt; apt;   point pt;   ap = getMinPoints(bp, points); // 获取与bp点距离最近的所有点   for (int x = 0; x &lt; ap.size(); x++) {     pt = bp;     sum = bfs(pt, ap[x]);     apt = points;     apt.erase(apt.begin() + x);     pt = ap[x]; // 设置为当前点     if (apt.size() &gt; 0) {       sum += getMinBfs(pt, idx, p, apt);       while (1) {         if (idx.size() &gt; 1) { // 有多个并列最近点的情况           int tmin = INT32_MAX, ts, k;           for (int i = 0; i &lt; idx.size(); i++) {             vector&lt;vector&lt;point&gt;&gt; tp = apt;             tp.erase(tp.begin() + idx[i]);             ts = getMinPath(apt[idx[i]][p[i]], ep,                             tp); // 计算以并列点为起点的路径             if (tmin &gt; ts) {               tmin = ts;               k = i;             } // 记录最小路径           }           idx[0] = idx[k], p[0] = p[k]; // 更新最小路径         }         pt = apt[idx[0]][p[0]];         apt.erase(apt.begin() + idx[0]);         if (apt.size() == 0)           break;         sum += getMinBfs(pt, idx, p, apt);       }     }     sum += bfs(pt, ep); // 加上到出口点的距离     if (minSum &gt; sum)       minSum = sum;   }   return minSum; } int main() {   cin &gt;&gt; n &gt;&gt; m;   for (int i = 0; i &lt; n; i++)     for (int j = 0; j &lt; m; j++) {       cin &gt;&gt; d[i][j];       if (d[i][j] != '#' &amp;&amp; d[i][j] != '.') {         base.push_back(item(point(i, j), d[i][j]));       }       if (d[i][j] == 'I')         bp = point(i, j);       if (d[i][j] == 'O')         ep = point(i, j);     }   // 扩展点,增加同方向的   for (int i = 0; i &lt; base.size(); i++) {     vector&lt;point&gt; vp;     if (base[i].c != 'I' &amp;&amp; base[i].c != 'O') {       vp = getpoints(base[i].c, base[i].pt);       pts.push_back(vp);     }   }   int sum1 = getMinPath(bp, ep, pts);          // 正向计算   int sum2 = getMinPath(ep, bp, pts);          // 反向计算   cout &lt;&lt; (sum1 &gt; sum2 ? sum2 : sum1) &lt;&lt; endl; // 取最小值   return 0; }</pre>
这道题暂未补解析。