滴滴 2023校招春季补录 后端研发试卷在线考试编程题2 20230312

黑白Logo
时间限制： 1000MS
内存限制： 65536KB
题目描述：
一家新公司请你帮他设计Logo。该Logo比较特别，是一个尺寸为 2^n X 2^n 的正方形图案，一些位置染上了黑色，其他位置则是白色。

Logo组成如下图：

其组成为：每次将该正方形的两条对称轴画出来，分割成 4 个尺寸相同的 2^(n-1) X 2^(n-1) 的正方形。如果这是第奇数次分割，就把左上和右下的正方形全部涂黑，剩下两个正方形继续分割；

如果这是第偶数次分割，就把左下和右上的正方形全部涂黑，剩下两个正方形继续分割；

直到不能分割为止。

现在，输入 n，你需要输出这个Logo的图案。由于输出可能会很多，只需要输出特定的 q 行的内容即可。

输入描述
第一行两个正整数 n,q；

接下来一行输入q个互不相同的正整数x1,x2,…,xq，表示需要依次输出该第x1行、第x2行,…，第xq行的内容。

对于所有的数据：
1≤n≤10，1≤q≤min(300,2n),1≤xi≤2n

输出描述
输出q行，表示第x1行,第x2行，…，第xq行的内容。其中，用W表示白色，用B表示黑色。

样例输入
2 4
1 2 3 4
样例输出
BBWB
BBBW
WBBB
BWBB

solution:暴力破解部分正确超时了，希望各路大佬能提供更加优秀的办法

#include 
#include 
using namespace std;int n, q, row;
char mat[1100][1100];
void dfs(int a, int b, int c, int d, int cnt){if (cnt == row + 1)return;//奇数if (cnt % 2){//左上for (int i = a; i <= (c - a) >> 1; ++i){for (int j = b; j <= (d - b) >> 1; ++j){mat[i][j] = 'B';}}//右下for (int i = (c - a + 1) >> 1; i <= c; ++i){for (int j = (d - b + 1) >> 1; j <= d; ++j){mat[i][j] = 'B';}}//右上dfs(a, (d - b) >> 1, (c - a + 1) >> 1, d, cnt + 1);//左下dfs((c - a + 1) >> 1, b, c, (d - b) >> 1, cnt + 1);}else {//左下for (int i = (c - a + 1) >> 1; i <= c; ++i){for (int j = b; j <= (d - b) >> 1; ++j){mat[i][j] = 'B';}}//右上for (int i = a; i <= (c - a + 1) >> 1; ++i){for (int j = (d - b) >> 1; j <= d; ++j){mat[i][j] = 'B';}}//左上dfs(a, b, (c - a) >> 1, (d - b) >> 1, cnt + 1);//右下dfs((c - a + 1) >> 1, (d - b + 1) >> 1, c, d, cnt + 1);}
}int main()
{cin >> n >> q;row = n;n = pow(2, n);for (int i = 0; i < n; ++i){for (int j = 0; j < n; ++j){mat[i][j] = 'W';}}dfs(0, 0, n - 1, n - 1, 1);while (q--){int temp;cin >> temp;for (int i = 0; i < n; ++i){cout << mat[temp - 1][i];}cout << endl;}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！