number_of_rects.cpp

#include <bits/stdc++.h>

// Reading input array:
std::vector<std::string> input() {
    int nRows, nCols;
    std::cin >> nRows >> nCols;
    std::vector<std::string> arr(nRows);
    for (int row = 0; row < nRows; ++row) {
        std::cin >> arr[row];
    }
    return arr;
}

// Solve for arr:
int solve(const std::vector<std::string>& arr) {
    const int nRows = (int)arr.size();
    const int nCols = (int)arr[0].size();
    // Calculate max length of '#' from pos (row, col) in side of increasing col:
    std::vector<std::vector<int>> maxLenRight(nRows, std::vector<int>(nCols+1, 0));
    for (int row = 0; row < nRows; ++row) {
        for (int col = nCols-1; col >= 0; --col) {
            if (arr[row][col] == '.') {
                maxLenRight[row][col] = 0;
            } else {
                maxLenRight[row][col] = maxLenRight[row][col+1] + 1;
            }
        }
    }
    // Calculate answer (with rectangles, which have height = 2):
    int answer = 0;
    for (int left = 0; left < nCols - 2; ++left) {
        // Group all points with col = left by maxLenRight and calc total count of then:
        int count = 0;
        std::vector<int> countWithLen(nCols, 0);
        for (int row = 0; row < nRows; ++row) {
            int len = maxLenRight[row][left];
            if (len >= 3) {
                countWithLen[len]++;
                count++;
            }
        }
        // Moving right border, increase answer, remove not interested lengths:
        for (int right = left + 2; right < nCols; ++right) {
            answer += count * (count-1) / 2;
            count -= countWithLen[right-left+1];
            countWithLen[right-left+1] = 0;
        }
    }
    // Decreasing number of rectangles with height = 2:
    for (int row1 = 0; row1 < nRows-1; ++row1) {
        const int row2 = row1+1;
        int same_len = 0;
        for (int col = 0; col < nCols; ++col) {
            if (arr[row1][col] == '#' && arr[row2][col] == '#') {
                same_len++;
            } else {
                if (same_len >= 3) {
                    answer -= (same_len-1) * (same_len-2) / 2;
                }
                same_len = 0;
            }
        }
        if (same_len >= 3) {
            answer -= (same_len-1) * (same_len-2) / 2;
        }
    }
    return answer;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(0); std::cout.tie(0);

    int nQueries; std::cin >> nQueries;
    for (int q = 0; q < nQueries; ++q) {
        std::cout << solve(input()) << std::endl;
    }

    return 0;
}