题解 | 剪纸游戏

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

int main(void) {
    int n, m;
    scanf("%d%d", &n, &m);
    char grid[1005][1005];
    for (int i = 0; i < n; i++)
        scanf("%s", grid[i]);
    int visited[1005][1005];
    memset(visited, 0, sizeof(visited));
    
    int front = 0, rear = 0;
    int qx[1005*1005], qy[1005*1005];
    qx[rear] = 0, qy[rear] = 0;
    rear++;

    int ans = 0;  //长方形连通块的数量
    //遍历每个格子
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            //判断当前格子是否是'.'且未被访问
            if (grid[i][j] == '.' && !visited[i][j]) {
                front = rear = 0;  // 清空队列
                qx[rear] = i;
				qy[rear] = j;
				rear++;
                visited[i][j] = 1;
                //初始化连通块的边界
                int min_x = i, max_x = i;
                int min_y = j, max_y = j;
                int cnt = 1;  // 连通块中'.'的数量
                //BFS遍历连通块
                while (front < rear) {
                    int x = qx[front];
					int y = qy[front];		    
					front++;
                    //更新边界
                    if (x < min_x) min_x = x;
                    if (x > max_x) max_x = x;
                    if (y < min_y) min_y = y;
                    if (y > max_y) max_y = y;
                    // 遍历四个方向
					int dx[4] = {-1, 1,  0, 0};
					int dy[4] = { 0, 0, -1, 1};
                    for (int k = 0; k < 4; k++) {
						int nx = x + dx[k];
						int ny = y + dy[k];
                        // 判断是否在网格内且为'.'且未访问
                        if (nx >= 0 && nx < n && ny >= 0 && ny < m){
							if(grid[nx][ny] == '.' && !visited[nx][ny]) {
                             	visited[nx][ny] = 1;
                            	qx[rear] = nx;
								qy[rear] = ny;
								rear++;
								cnt++;
							}
                        }
                    }
                }
                // 计算包围盒的面积
                int area = (max_x - min_x + 1) * (max_y - min_y + 1);
                // 如果连通块中'.'的数量等于包围盒面积则是长方形
                if (cnt == area)
                    ans++;
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}