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

安全地图 在未来的星际探索中,人类发现了一个由 (2 n )×(2 n ) 个星球组成的正方形星域。人类决定在这些星球上建立基地,但需要识别安全星球。规划规则如…

安全地图

在未来的星际探索中,人类发现了一个由 (2n)×(2n) 个星球组成的正方形星域。人类决定在这些星球上建立基地,但需要识别安全星球。规划规则如下:

(1)将整个星域均分为 4 个更小的正方形区域;

(2)左上角区域的所有星球都是安全的(用 "." 表示);

(3)其余三个区域继续递归划分,直到区域只有一个星球;

(4)未被标记为安全的星球存在危险(用 "*" 表示)。

请根据划分规则,输出整个星域的安全地图。

时间限制:1000ms,内存限制:256MB

输入格式

一个整数 n,表示星域大小。

输出格式

输出每个星球的安全性。


输入样例

3

输出样例

.......*
......**
.....*.*
....****
...*...*
..**..**
.*.*.*.*
********

数据范围:

1≤n≤12。

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;stdio.h&gt; #include &lt;stdlib.h&gt; #include &lt;string.h&gt; char** map; // 递归函数:划分区域并标记安全星球 // x, y:当前区域左上角坐标 // size:当前区域的大小(size = 2^k) void divide(int x, int y, int size) {     if (size == 1) {         // 最小区域,若不是左上角子区域(即递归到最底层的非左上角区域),标记为'*'         map[x][y] = '*';         return;     }     int half = size / 2;     // 左上角区域标记为安全     for (int i = x; i &lt; x + half; i++) {         for (int j = y; j &lt; y + half; j++) {             map[i][j] = '.';         }     }     // 递归处理其余三个区域     divide(x, y + half, half);          // 右上角     divide(x + half, y, half);          // 左下角     divide(x + half, y + half, half);   // 右下角 } int main() {     int n;     scanf("%d", &amp;n);     int size = 1 &lt;&lt; n;  // 计算2^n     // 初始化地图,分配内存     map = (char**)malloc(size * sizeof(char*));     for (int i = 0; i &lt; size; i++) {         map[i] = (char*)malloc((size + 1) * sizeof(char));  // +1 用于存储字符串结束符         memset(map[i], 0, size + 1);     }     // 从整个区域开始划分     divide(0, 0, size);     // 输出地图     for (int i = 0; i &lt; size; i++) {         printf("%s\n", map[i]);         free(map[i]);  // 释放每行内存     }     free(map);  // 释放地图指针数组     return 0; }</pre>
这道题暂未补解析。