服务器布局_图森未来笔试题

图森未来最近购入了一批服务器，它们大小分别是2*4、4*8、8*16、……、(2^k)*(2^(k+1))，即每台服务器都恰好可以被四台比它们更小的服务器代替。
现在，公司的员工小图被分配了一个任务，那就是根据小森给出的服务器分配方式文档安排服务器的位置。

小森交给小图的文档见输入样例。这个文档遵循简化的yaml格式，但是你不需要提前知道什么是yaml。

简而言之，在这个文档中：

每一行都以两个字母和一个半角冒号开头，字母是"NW"、"NE"、"SW"、"SE"中的一个，且在同一层级不会重复；
"NW"、"NE"、"SW"和"SE"分别代表当前层级的左上角、右上角、左下角和右下角位置，即上方为北，右方为东；
若冒号后有一个空格和"O"、"X"中的一个字母，则表示这一行是当前层级的一台服务器；
若冒号后没有任何内容（即冒号后是换行符），则接下来的若干行一定比当前行多两个空格的缩进，且被缩进的行除缩进外也符合以上全部规则；
缩进可以嵌套。

以输入样例中的文档为例，小图需要生成的服务器位置安排见输出样例。其中遵循的规则是：

最深层级的服务器大小一定是2*4，在图中用一个3行5列的矩阵表示；
相邻的服务器会共享同一条相邻边；
除了最深层级的服务器，每一台服务器的大小都与它下一层级的四台服务器以2*2的方式拼接起来相同；
所有服务器的角落都用加号"+"表示，除此之外所有服务器的水平边界用减号"-"表示，垂直边界用竖线"|"表示，服务器的正中心位置根据文档内容用"X"或"O"中的一个字符表示，其它位置用空格表示。

现在小图希望你可以帮他写一个程序，给出一份文档，输出对应的服务器位置安排的字符图案。

输入为符合题目描述中条件的一个文档。

文档保证：
- 第1层级即最高层级有且仅有四个元素；
- 对任意正整数k>=1，每个第k层级的元素下：或者没有嵌套元素但有一个"O"、"X"之一的标签，或者有且仅有四个k+1层级的嵌套元素；
- 任何层级下的四个元素都分别为"NW"、"NE"、"SW"和"SE"中的一个，不会缺少也不会重复；
- 最深的层级不会超过8。

输出

+---------------+---------------+
|               |               |
|               |               |
|               |               |
|       X       |       O       |
|               |               |
|               |               |
|               |               |
+---------------+---+---+-------+
|               | X | O |       |
|               +---+---+   O   |
|               | X | O |       |
|       O       +---+---+-------+
|               |       |       |
|               |   O   |   X   |
|               |       |       |
+---------------+-------+-------+

#include <iostream> #include <algorithm> using namespace std; struct Block { bool isBase; union { bool O; struct Block *nxt[4]; }; }; int depth; Block *last_father[10]; char canvas[(2 << 9) + 10][(2 << 10) + 10]; void dfs(Block *blk, int dep, int x_offset, int y_offset) { int height = 2 << (depth - dep + 1); int weight = height << 1; if (blk->isBase) { for (int i = x_offset + 1; i < x_offset + height; i++) { if (!canvas[i][y_offset]) canvas[i][y_offset] = '|'; if (!canvas[i][y_offset + weight]) canvas[i][y_offset + weight] = '|'; } for (int i = y_offset + 1; i < y_offset + weight; i++) { if (!canvas[x_offset][i]) canvas[x_offset][i] = '-'; if (!canvas[x_offset + height][i]) canvas[x_offset + height][i] = '-'; } canvas[x_offset][y_offset] = '+'; canvas[x_offset][y_offset + weight] = '+'; canvas[x_offset + height][y_offset] = '+'; canvas[x_offset + height][y_offset + weight] = '+'; canvas[x_offset + (height >> 1)][y_offset + (weight >> 1)] = blk->O ? 'O' : 'X'; } else { for (int i = 0; i < 4; i++) { dfs(blk->nxt[i], dep + 1, x_offset + ((i & 2) ? (height >> 1) : 0), y_offset + ((i & 1) ? (weight >> 1) : 0)); } } } void yaml(char line[50], int &layer, int &dir, char &type) { char *ch = line; layer = 0; dir = 0; while (*ch == ' ') { layer++; ch++; } layer >>= 1; if (*ch == 'S') { dir += 2; } ch++; if (*ch == 'E') { dir += 1; } ch++; while (*ch && *ch != 'O' && *ch != 'X') { ch++; } type = *ch; } int main() { char line[50]; Block root; last_father[0] = &root; root.isBase = false; while (cin.getline(line, 50)) { int layer, dir; char type; yaml(line, layer, dir, type); Block *father = last_father[layer]; depth = max(depth, layer); father->nxt[dir] = new Block(); switch (type) { case 'O': father->nxt[dir]->isBase = true; father->nxt[dir]->O = true; break; case 'X': father->nxt[dir]->isBase = true; father->nxt[dir]->O = false; break; default: father->nxt[dir]->isBase = false; last_father[layer + 1] = father->nxt[dir]; } } dfs(&root, 0, 0, 0); int height = 2 << (depth + 1); int weight = 2 << (depth + 2); for (int i = 0; i <= height; i++) { for (int j = 0; j <= weight; j++) { if (canvas[i][j]) putchar(canvas[i][j]); else putchar(' '); } if (i != height) putchar('\n'); } return 0; }

服务器布局

输入描述:

输出描述:

输入

输出

问题信息

热门推荐

相关试题