题意分析

本题要求编写一个程序，根据输入的路径信息，在一个32x32的位图中围绕封闭路径绘制边界。路径是封闭的且按逆时针方向运行，边界像素总是在路径的“右侧”。输入文件包含多个测试用例，每个测试用例由路径起点坐标和表示路径的字符串组成，字符串中包含'W'（西）、'E'（东）、'N'（北）、'S'（南）和'.'（路径结束）。输出要求为每个测试用例输出一行“Bitmap #n”，然后按行输出位图，设置的位打印'X'，未设置的位打印'.'，每个位图后输出一个空行。

解题思路

1. 初始化：
   • 读取测试用例数量n。
   • 初始化一个32x32的字符数组ch，用于存储位图，初始值全部为'.'。
2. 处理每个测试用例：
   • 读取路径的起点坐标x和y。
   • 读取表示路径的字符串，根据字符更新路径并在相应位置设置'X'。
   • 对于'W'（西），将当前位置的左边一格设置为'X'，并更新x坐标。
   • 对于'E'（东），将当前位置的右边一格设置为'X'，并更新x坐标。
   • 对于'N'（北），将当前位置的上边一格设置为'X'，并更新y坐标。
   • 对于'S'（南），将当前位置的下边一格设置为'X'，并更新y坐标。
   • 当遇到'.'时，表示路径结束，开始输出当前测试用例的位图。
3. 输出位图：
   • 输出“Bitmap #n”，其中n为测试用例编号。
   • 按行输出位图，每行从左到右输出每个位置的字符。
   • 输出完一个位图后，输出一个空行。

复杂度分析

1. 时间复杂度：
   • 对于每个测试用例，初始化位图的时间复杂度为$O(32\times32)$。
   • 处理路径字符串的时间复杂度为$O(len)$，其中len为路径字符串的长度。
   • 输出位图的时间复杂度为$O(32\times32)$。
   • 总体时间复杂度为$O(n\times(32\times32 + len))$，其中n为测试用例数量。
2. 空间复杂度：
   • 存储位图的字符数组ch大小为32x32，空间复杂度为$O(32\times32)$。
   • 其他变量如x、y、d等占用常数级空间。
   • 总体空间复杂度为$O(32\times32)$。

代码实现

#include<stdio.h>
#include<string.h>

int main()
{
    char ch[33][33], d;
    int i, j, x, y, k, n;
    scanf("%d", &n);
    k = 0;
    while (n--)
    {
        scanf("%d%d", &x, &y);
        // 初始化位图
        for (i = 1; i <= 32; i++)
            for (j = 1; j <= 32; j++)
                ch[i][j] = '.';
        scanf("%c", &d);
        while (d!= '.')
        {
            if (d == 'E')
            {
                x++;
                ch[32 - y + 1][x] = 'X';
            }
            if (d == 'N')
            {
                y++;
                ch[32 - y + 1][x + 1] = 'X';
            }
            if (d == 'W')
            {
                ch[32 - y][x] = 'X';
                x--;
            }
            if (d == 'S')
            {
                ch[32 - y + 1][x] = 'X';
                y--;
            }
            scanf("%c", &d);
        }
        k++;
        // 输出位图
        printf("Bitmap #%d\n", k);
        for (i = 1; i <= 32; i++)
        {
            for (j = 1; j <= 32; j++) printf("%c", ch[i][j]);
            printf("\n");
        }
        printf("\n");
    }
    return 0;
}