naive.cpp

#pragma GCC diagnostic ignored "-Wunused-result"
#include <stdio.h>
#include <bits/stdc++.h>

// Generate random test
std::vector<std::string> gen_test(const int nRows, const int nCols, const int nRects) {
    std::vector<std::string> arr(nRows, std::string(nCols, '.'));
    for (int id = 0; id < nRects; ++id) {
        int r1 = std::rand() % nRows;
        int r2 = std::rand() % nRows;
        int c1 = std::rand() % nCols;
        int c2 = std::rand() % nCols;
        if (r1 > r2) std::swap(r1, r2);
        if (c1 > c2) std::swap(c1, c2);
        for (int c = c1; c <= c2; ++c) arr[r1][c] = arr[r2][c] = '#';
        for (int r = r1; r <= r2; ++r) arr[r][c1] = arr[r][c2] = '#';
    }
    return arr;
}

// Generate random number in [a, b]
int rand_number(int a, int b) {
    return std::rand() % (b - a + 1) + a;
}

// Generate set of random tests
void gen(int nTests) {
    std::srand(std::time(0));
    for (int i = 0; i < nTests; ++i) {
        const int nRows = rand_number(5, 20);
        const int nCols = rand_number(5, 20);
        const int nRects = rand_number(0, 20);
        auto arr = gen_test(nRows, nCols, nRects);
        std::cout << nRows << " " << nCols << "\n";
        for (auto& row : arr) {
            std::cout << row << "\n";
        }
    }
    std::exit(0);
}

int main() {
    //gen(1000);
    int nRows, nCols;
    while (scanf("%d %d", &nRows, &nCols) == 2) {
        std::vector<std::string> arr(nRows);
        for (int i = 0; i < nRows; ++i) {
            char buf[351];
            scanf("%350s", buf);
            arr[i] = buf;
        }

        std::vector<std::vector<int>> sum(nRows+1, std::vector<int>(nCols+1));
        for (int row = nRows-1; row >= 0; --row) {
            for (int col = nCols-1; col >= 0; --col) {
                sum[row][col] = (arr[row][col] == '#') + sum[row+1][col] + sum[row][col+1] - sum[row+1][col+1];
            }
        }

        std::function<int(int, int, int, int)> sum_in_rect = [&](const int r1, const int c1, const int r2, const int c2) {
            return sum[r1][c1] - sum[r2+1][c1] - sum[r1][c2+1] + sum[r2+1][c2+1];
        };

        std::function<bool(int, int, int, int)> is_rect = [&](const int r1, const int c1, const int r2, const int c2) {
            return sum_in_rect(r1, c1, r2, c2) - sum_in_rect(r1+1, c1+1, r2-1, c2-1) == 2*(r2-r1+c2-c1);
        };

        long long answ = 0;
        for (int r1 = 0; r1 < nRows-2; ++r1) {
            for (int c1 = 0; c1 < nCols-2; ++c1) {
                for (int r2 = r1+2; r2 < nRows; ++r2) {
                    for (int c2 = c1+2; c2 < nCols; ++c2) {
                        answ += is_rect(r1, c1, r2, c2);
                    }
                }
            }
        }
        printf("%lld\n", answ);
    }
    return 0;
}