1 条题解

  • 0
    @ 2025-10-2 14:20:53
    #include <bits/stdc++.h>
    using namespace std;
    int n, m;
    int g[505][505];
    int sum[505][505];
    int getSum(int u, int d, int l, int r)
    {
        return sum[d][r] -
               sum[d][l - 1] -
               sum[u - 1][r] +
               sum[u - 1][l - 1];
    }
    int main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
        cin >> n >> m;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
            {
                char c;
                cin >> c;
                g[i][j] = (c == '#');
            }
    
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                sum[i][j] = sum[i - 1][j] + sum[i][j - 1] -
                            sum[i - 1][j - 1] + g[i][j];
        long long ans = 0;
        for (int u = 1; u <= n; u++)
            for (int d = u; d <= n; d++)
            {
                for (int l = 1, r = l - 1; l <= m; l++)
                {
                    // 把 r 调整到第一个符合要求的位置。
                    // l~r 就都符合要求
                    for (; r + 1 <= m && getSum(u, d, l, r + 1) <= 1; r++)
                        ;
                    ans += r - l + 1;
                }
            }
        cout << ans << "\n";
        return 0;
    }
    
    • 1

    信息

    ID
    108
    时间
    1000ms
    内存
    512MiB
    难度
    8
    标签
    递交数
    53
    已通过
    9
    上传者