简答题
偏难
#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 <stdio.h>
#include <stdlib.h>
#include <string.h>
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 < x + half; i++) {
for (int j = y; j < 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", &n);
int size = 1 << n; // 计算2^n
// 初始化地图,分配内存
map = (char**)malloc(size * sizeof(char*));
for (int i = 0; i < 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 < size; i++) {
printf("%s\n", map[i]);
free(map[i]); // 释放每行内存
}
free(map); // 释放地图指针数组
return 0;
}</pre>
这道题暂未补解析。