题目链接

剪纸游戏

题目描述

在一张由 . 和 * 组成的 网格纸上，. 代表被剪去的小方格，* 代表保留的小方格。被剪下的图案都是由 . 构成的、互相不连通的区域。你需要计算，在所有被剪下来的图案中，有多少个是长方形（正方形被视为特殊的长方形）。

解题思路

这个问题可以分解为两个主要步骤：

  1. 找出所有被剪掉的图案：每个图案都是一个由 . 组成的连通块。
  2. 判断每个图案的形状：检查每个连通块是否构成一个实心的长方形。

我们可以通过图的遍历算法，如广度优先搜索 (BFS) 或深度优先搜索 (DFS)，来系统地解决这个问题。

算法步骤如下：

  1. 遍历网格：

    • 我们使用一个 visited 二维数组来记录哪些格子已经被访问过，以避免重复处理。
    • 从头到尾遍历输入网格的每一个格子 (i, j)。

  2. 发现新图案：

    • 如果在 (i, j) 处发现一个尚未访问过的 . 格子，那么我们就找到了一个新图案的“一部分”。
    • 从这个格子开始，我们启动一次 BFS 来找到这个图案所包含的全部 . 格子。

  3. BFS 寻找连通块：

    • 创建一个队列，并将起始格子 (i, j) 入队。同时，将其标记为已访问。
    • 创建一个临时列表 component_cells，用于存储当前图案的所有格子的坐标。
    • 当队列不为空时，出队一个格子，并将其四个方向的邻居（如果合法且为 .）入队并标记为已访问，同时将它们的坐标也加入 component_cells。
    • BFS 结束后，component_cells 就包含了当前这个被剪掉图案的完整形状。

  4. 判断是否为长方形：

    • 对 component_cells 列表中的所有坐标，找到它们行和列的最大值与最小值，从而确定这个图案的边界框 (Bounding Box)。
    • 计算边界框的理论面积：area = (max_row - min_row + 1) * (max_col - min_col + 1)。
    • 将理论面积与图案中格子的实际数量（即 component_cells 的大小）进行比较。
    • 如果两者相等，说明这个图案是一个没有任何空洞的实心长方形。我们就在计数器上加一。

  5. 重复：

    • 继续遍历网格，直到所有格子都被检查过。最终得到的计数就是答案。

这个方法确保了每个 . 格子只被访问一次，因此算法是高效的，其时间复杂度和空间复杂度均为 。

代码

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>

using namespace std;

// BFS 寻找一个完整的 '.' 连通块
void bfs(int r, int c, int n, int m, const vector<string>& grid, 
         vector<vector<bool>>& visited, vector<pair<int, int>>& component) {
    
    queue<pair<int, int>> q;
    q.push({r, c});
    visited[r][c] = true;
    component.push_back({r, c});

    int dx[] = {-1, 1, 0, 0};
    int dy[] = {0, 0, -1, 1};

    while (!q.empty()) {
        pair<int, int> curr = q.front();
        q.pop();

        for (int i = 0; i < 4; ++i) {
            int nr = curr.first + dx[i];
            int nc = curr.second + dy[i];

            if (nr >= 0 && nr < n && nc >= 0 && nc < m &&
                grid[nr][nc] == '.' && !visited[nr][nc]) {
                
                visited[nr][nc] = true;
                q.push({nr, nc});
                component.push_back({nr, nc});
            }
        }
    }
}

// 检查一个连通块是否为长方形
bool is_rectangle(const vector<pair<int, int>>& component) {
    if (component.empty()) {
        return false;
    }
    int min_r = component[0].first, max_r = component[0].first;
    int min_c = component[0].second, max_c = component[0].second;

    for (const auto& cell : component) {
        min_r = min(min_r, cell.first);
        max_r = max(max_r, cell.first);
        min_c = min(min_c, cell.second);
        max_c = max(max_c, cell.second);
    }

    int height = max_r - min_r + 1;
    int width = max_c - min_c + 1;

    return component.size() == (size_t)height * width;
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<string> grid(n);
    for (int i = 0; i < n; ++i) {
        cin >> grid[i];
    }

    vector<vector<bool>> visited(n, vector<bool>(m, false));
    int rectangle_count = 0;

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (grid[i][j] == '.' && !visited[i][j]) {
                vector<pair<int, int>> component_cells;
                bfs(i, j, n, m, grid, visited, component_cells);
                if (is_rectangle(component_cells)) {
                    rectangle_count++;
                }
            }
        }
    }

    cout << rectangle_count << endl;

    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        char[][] grid = new char[n][m];
        for (int i = 0; i < n; i++) {
            grid[i] = sc.next().toCharArray();
        }

        boolean[][] visited = new boolean[n][m];
        int rectangleCount = 0;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == '.' && !visited[i][j]) {
                    List<int[]> componentCells = new ArrayList<>();
                    bfs(i, j, n, m, grid, visited, componentCells);
                    if (isRectangle(componentCells)) {
                        rectangleCount++;
                    }
                }
            }
        }
        System.out.println(rectangleCount);
    }

    private static void bfs(int r, int c, int n, int m, char[][] grid, 
                            boolean[][] visited, List<int[]> component) {
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{r, c});
        visited[r][c] = true;
        component.add(new int[]{r, c});

        int[] dr = {-1, 1, 0, 0};
        int[] dc = {0, 0, -1, 1};

        while (!q.isEmpty()) {
            int[] curr = q.poll();
            for (int i = 0; i < 4; i++) {
                int nr = curr[0] + dr[i];
                int nc = curr[1] + dc[i];

                if (nr >= 0 && nr < n && nc >= 0 && nc < m &&
                    grid[nr][nc] == '.' && !visited[nr][nc]) {
                    
                    visited[nr][nc] = true;
                    q.offer(new int[]{nr, nc});
                    component.add(new int[]{nr, nc});
                }
            }
        }
    }

    private static boolean isRectangle(List<int[]> component) {
        if (component.isEmpty()) return false;

        int minR = component.get(0)[0], maxR = component.get(0)[0];
        int minC = component.get(0)[1], maxC = component.get(0)[1];

        for (int[] cell : component) {
            minR = Math.min(minR, cell[0]);
            maxR = Math.max(maxR, cell[0]);
            minC = Math.min(minC, cell[1]);
            maxC = Math.max(maxC, cell[1]);
        }

        int height = maxR - minR + 1;
        int width = maxC - minC + 1;

        return component.size() == height * width;
    }
}

import sys
from collections import deque

def is_rectangle(component):
    if not component:
        return False
    
    min_r = min(cell[0] for cell in component)
    max_r = max(cell[0] for cell in component)
    min_c = min(cell[1] for cell in component)
    max_c = max(cell[1] for cell in component)

    height = max_r - min_r + 1
    width = max_c - min_c + 1
    
    return len(component) == height * width

def bfs(r, c, n, m, grid, visited):
    component_cells = []
    q = deque([(r, c)])
    visited[r][c] = True
    component_cells.append((r, c))

    dr = [-1, 1, 0, 0]
    dc = [0, 0, -1, 1]

    while q:
        curr_r, curr_c = q.popleft()
        
        for i in range(4):
            nr, nc = curr_r + dr[i], curr_c + dc[i]
            
            if 0 <= nr < n and 0 <= nc < m and \
               grid[nr][nc] == '.' and not visited[nr][nc]:
                
                visited[nr][nc] = True
                q.append((nr, nc))
                component_cells.append((nr, nc))
    
    return component_cells

def main():
    n, m = map(int, sys.stdin.readline().split())
    grid = [sys.stdin.readline().strip() for _ in range(n)]

    visited = [[False] * m for _ in range(n)]
    rectangle_count = 0

    for i in range(n):
        for j in range(m):
            if grid[i][j] == '.' and not visited[i][j]:
                component = bfs(i, j, n, m, grid, visited)
                if is_rectangle(component):
                    rectangle_count += 1
    
    print(rectangle_count)

if __name__ == "__main__":
    main()

算法及复杂度

  • 算法：广度优先搜索 (BFS) + 几何形状判断
  • 时间复杂度：我们遍历网格中的每个单元格。每个单元格最多被访问一次（在主循环中被检查）和处理一次（在BFS中入队和出队）。因此，总的时间复杂度是 ，其中 和 是网格的行数和列数。
  • 空间复杂度：空间主要由 visited 数组和BFS队列消耗。visited 数组的大小是 。在最坏的情况下，队列可能需要存储网格中的所有 . 单元格。因此，总的空间复杂度是 。