题解 | 剪纸游戏

#include <stdio.h>

int n, m;
char maze[1005][1005];
// int vis[1005][1005];  //本次不使用标记数组，而是遇到'.'后把它入队，随即把此位置改成一个特殊字符'#'表示已访问过
int dir[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};

int num;

typedef struct node
{
    int x;
    int y;
} Node;

Node queue[1000000];


void bfs(int x, int y)
{
    
    int head = 0, tail = 0;
    int size = 1; //用来记录被剪下的区域的大小，即'.'的个数
    int maxx = x, maxy = y; //用来记录此区域的最大/最小x、y坐标值，即边界，
    int minx = x, miny = y; //计算面积area =（maxx-minx+1）*（maxy-miny+1），若area != size，说明此区域不是长方形

    //起点入队,入队从队尾入
    queue[tail].x = x;
    queue[tail].y = y;
    maze[x][y] = '#';    //做标记
    tail++;

    while (head < tail)
    {
        //出队，出队从队首出
        int x = queue[head].x;
        int y = queue[head].y;
        head++;

        for (int i = 0; i < 4; i++)
        {
            int nx = x + dir[i][0];
            int ny = y + dir[i][1];
            
            if (maze[nx][ny] == '.') //寻找到新的'.'，入队
            {
                queue[tail].x = nx;
                queue[tail].y = ny;
                maze[nx][ny] = '#'; //做标记
                tail++;

                size++; //更新区域大小
                if (nx > maxx) //更新
                    maxx = nx;
                if (ny > maxy)
                    maxy = ny;
                if (nx < minx)
                    minx = nx;
                if (ny < miny)
                    miny = ny;
            }
        }
    }
    //搜索结束，进行判断
    if (size == (maxx-minx+1)*(maxy-miny+1))
    {
        num++;
    }
}   

int main() 
{
    num = 0; //初始化计数值
    scanf("%d %d\n", &n, &m);
    for (int i = 0; i < n; i++)
    {
        scanf("%s", maze[i]);
    }

    // for (int i = 0; i < n; i++)
    // {
    //     printf("%s\n", maze[i]);

    // }

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (maze[i][j] == '.')
            {
                bfs(i, j);
            }            
        }
    }


    printf("%d", num);

    return 0;
}