题目链接

剪纸游戏

题目描述

给定一张由 '.' 与 '*' 组成的 矩阵，'.' 表示被剪去的小方格，'*' 表示仍保留的小方格。'.' 的每个连通块（按四方向连通）对应一个被剪下的图案。问被剪下来的图案中，有多少个是长方形（正方形视为特殊的长方形）。

输入：

  • 第一行两个整数：、
  • 接下来 行，每行一个长度为 的字符串，仅包含 '.' 与 '*'

输出：

  • 一个整数，表示长方形图案的数量

解题思路

将每个 '.' 连通块视为一个图案，判断其是否为长方形：

  • 用 BFS/DFS 在四方向（上下左右）上寻找 '.' 的连通块；统计该块的格子数 ，同时记录最小行、最大行、最小列、最大列，得到外接矩形大小 、。
  • 若 ，则该连通块恰好充满其外接矩形，即为一个长方形；否则不是。

说明：由于剪裁沿网格线进行，一个被剪下的长方形应当在四连通意义下形成一个完全填充的矩形区域。上述判定等价且线性。

代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<string> g(n);
    for (int i = 0; i < n; ++i) cin >> g[i];

    vector<vector<int>> vis(n, vector<int>(m, 0));
    const int dx[4] = {1, -1, 0, 0};
    const int dy[4] = {0, 0, 1, -1};

    long long ans = 0;
    queue<pair<int,int>> q;

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (g[i][j] == '.' && !vis[i][j]) {
                int minR = i, maxR = i, minC = j, maxC = j;
                int cnt = 0;
                vis[i][j] = 1;
                q.push(make_pair(i, j));
                while (!q.empty()) {
                    pair<int,int> cur = q.front();
                    q.pop();
                    int x = cur.first, y = cur.second;
                    ++cnt;
                    if (x < minR) minR = x; if (x > maxR) maxR = x;
                    if (y < minC) minC = y; if (y > maxC) maxC = y;
                    for (int d = 0; d < 4; ++d) {
                        int nx = x + dx[d];
                        int ny = y + dy[d];
                        if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                        if (vis[nx][ny] || g[nx][ny] != '.') continue;
                        vis[nx][ny] = 1;
                        q.push(make_pair(nx, ny));
                    }
                }
                int h = maxR - minR + 1;
                int w = maxC - minC + 1;
                if (cnt == h * w) ++ans;
            }
        }
    }

    cout << ans << "\n";
    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[][] g = new char[n][m];
        for (int i = 0; i < n; i++) {
            String s = sc.next();
            g[i] = s.toCharArray();
        }

        boolean[][] vis = new boolean[n][m];
        int[] dx = {1, -1, 0, 0};
        int[] dy = {0, 0, 1, -1};
        long ans = 0;
        ArrayDeque<int[]> q = new ArrayDeque<>();

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (g[i][j] == '.' && !vis[i][j]) {
                    int minR = i, maxR = i, minC = j, maxC = j;
                    int cnt = 0;
                    vis[i][j] = true;
                    q.add(new int[]{i, j});
                    while (!q.isEmpty()) {
                        int[] cur = q.poll();
                        int x = cur[0], y = cur[1];
                        cnt++;
                        if (x < minR) minR = x; if (x > maxR) maxR = x;
                        if (y < minC) minC = y; if (y > maxC) maxC = y;
                        for (int d = 0; d < 4; d++) {
                            int nx = x + dx[d];
                            int ny = y + dy[d];
                            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                            if (vis[nx][ny] || g[nx][ny] != '.') continue;
                            vis[nx][ny] = true;
                            q.add(new int[]{nx, ny});
                        }
                    }
                    int h = maxR - minR + 1;
                    int w = maxC - minC + 1;
                    if (cnt == h * w) ans++;
                }
            }
        }
        System.out.println(ans);
    }
}

from collections import deque

n, m = map(int, input().split())
grid = [input().strip() for _ in range(n)]
vis = [[False] * m for _ in range(n)]

dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
ans = 0

for i in range(n):
    for j in range(m):
        if grid[i][j] == '.' and not vis[i][j]:
            minr = maxr = i
            minc = maxc = j
            cnt = 0
            q = deque([(i, j)])
            vis[i][j] = True
            while q:
                x, y = q.popleft()
                cnt += 1
                if x < minr: minr = x
                if x > maxr: maxr = x
                if y < minc: minc = y
                if y > maxc: maxc = y
                for dx, dy in dirs:
                    nx, ny = x + dx, y + dy
                    if 0 <= nx < n and 0 <= ny < m and not vis[nx][ny] and grid[nx][ny] == '.':
                        vis[nx][ny] = True
                        q.append((nx, ny))
            h = maxr - minr + 1
            w = maxc - minc + 1
            if cnt == h * w:
                ans += 1

print(ans)

算法及复杂度

  • 算法：枚举 '.' 连通块（四方向），按“连通块大小等于外接矩形面积”判定是否为长方形
  • 时间复杂度：（每个格子至多入队一次）
  • 空间复杂度：（访问数组与队列在最坏情况下同量级）