Author: loop3r
Date: 20260224
tag: 枚举
link: https://www.luogu.com.cn/problem/P3654

问题描述

link

分析

横向处理：对于每一行，统计连续的 . 的长度，如果长度 $len$ 大于等于 $k$，则答案加上 $len-k+1$。

纵向处理：对于每一列，统计连续的 . 的长度，如果长度 $len$ 大于等于 $k$，则答案加上 $len-k+1$。

注意：当 $k=1$ 时，横向和纵向会重复计算，因此纵向处理时需要判断 $k>1$。

参考代码

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

int n, m, k;
char g[105][105];

int main() {
    cin >> n >> m >> k;
    for (int i = 0; i < n; i++) cin >> g[i];

    int ans = 0;

    // 横向
    for (int i = 0; i < n; i++) {
        int len = 0;
        for (int j = 0; j < m; j++) {
            if (g[i][j] == '.') {
                len++;
            } else {
                if (len >= k) ans += len - k + 1;
                len = 0;
            }
        }
        if (len >= k) ans += len - k + 1;
    }

    // 纵向
    if (k > 1) {  // 避免 k=1 重复
        for (int j = 0; j < m; j++) {
            int len = 0;
            for (int i = 0; i < n; i++) {
                if (g[i][j] == '.') {
                    len++;
                } else {
                    if (len >= k) ans += len - k + 1;
                    len = 0;
                }
            }
            if (len >= k) ans += len - k + 1;
        }
    }

    cout << ans << endl;

    return 0;
}