Submission #66780646

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// Original Python code:
/*
for _ in range(int(input())):
    h, w = map(int, input().split())
    grid = [input() for _ in range(h)]
    if h > w:
        grid = [''.join(grid[i][j] for i in range(h)) for j in range(w)]
        h, w = w, h
    a = [[1 if ch == '#' else -1 for ch in row] for row in grid]
    pre = [[0]*w for _ in range(h+1)]
    for i in range(h):
        for j in range(w):
            pre[i+1][j] = pre[i][j] + a[i][j]
    ans = 0
    for u in range(h):
        for d in range(u, h):
            cnt = {0: 1}
            s = 0
            for j in range(w):
                col_sum = pre[d+1][j] - pre[u][j]
                s += col_sum
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

// Original Python code:
/*
for _ in range(int(input())):
    h, w = map(int, input().split())
    grid = [input() for _ in range(h)]
    if h > w:
        grid = [''.join(grid[i][j] for i in range(h)) for j in range(w)]
        h, w = w, h
    a = [[1 if ch == '#' else -1 for ch in row] for row in grid]
    pre = [[0]*w for _ in range(h+1)]
    for i in range(h):
        for j in range(w):
            pre[i+1][j] = pre[i][j] + a[i][j]
    ans = 0
    for u in range(h):
        for d in range(u, h):
            cnt = {0: 1}
            s = 0
            for j in range(w):
                col_sum = pre[d+1][j] - pre[u][j]
                s += col_sum
                ans += cnt.get(s, 0)
                cnt[s] = cnt.get(s, 0) + 1
    print(ans)
*/

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

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

    int T;
    cin >> T;
    while (T--) {
        int h, w;
        cin >> h >> w;
        vector<string> grid(h);
        for (int i = 0; i < h; i++) {
            cin >> grid[i];
        }

        if (h > w) {
            // transpose
            vector<string> ng(w, string(h, ' '));
            for (int i = 0; i < h; i++) {
                for (int j = 0; j < w; j++) {
                    ng[j][i] = grid[i][j];
                }
            }
            grid = move(ng);
            swap(h, w);
        }

        // map to +1 (#) and -1 (.)
        vector<vector<int>> a(h, vector<int>(w));
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                a[i][j] = (grid[i][j] == '#') ? 1 : -1;
            }
        }

        // prefix sum over rows for each column
        vector<vector<int>> pre(h+1, vector<int>(w, 0));
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                pre[i+1][j] = pre[i][j] + a[i][j];
            }
        }

        long long ans = 0;
        for (int u = 0; u < h; u++) {
            for (int d = u; d < h; d++) {
                unordered_map<long long, long long> cnt;
                cnt.reserve(w*2);
                cnt[0] = 1;
                long long s = 0;
                for (int j = 0; j < w; j++) {
                    int col_sum = pre[d+1][j] - pre[u][j];
                    s += col_sum;
                    auto it = cnt.find(s);
                    if (it != cnt.end()) {
                        ans += it->second;
                        it->second++;
                    } else {
                        cnt[s] = 1;
                    }
                }
            }
        }

        cout << ans << "\n";
    }

    return 0;
}

Submission Info

Judge Result