Submission #66778325

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/*
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
    MAX_S = h * w
    SIZE = 2 * MAX_S + 1
    OFFSET = MAX_S
    for u in range(h):
        for d in range(u, h):
            cnt = [0] * SIZE
            cnt[OFFSET] = 1
            s = 0
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

/*
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
    MAX_S = h * w
    SIZE = 2 * MAX_S + 1
    OFFSET = MAX_S
    for u in range(h):
        for d in range(u, h):
            cnt = [0] * SIZE
            cnt[OFFSET] = 1
            s = 0
            for j in range(w):
                col_sum = pre[d+1][j] - pre[u][j]
                s += col_sum
                idx = s + OFFSET
                ans += cnt[idx]
                cnt[idx] += 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) {
            vector<string> trans(w, string(h, ' '));
            for (int i = 0; i < h; i++) {
                for (int j = 0; j < w; j++) {
                    trans[j][i] = grid[i][j];
                }
            }
            grid.swap(trans);
            swap(h, w);
        }

        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;
            }
        }

        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;
        int MAX_S = h * w;
        int SIZE = 2 * MAX_S + 1;
        int OFFSET = MAX_S;

        for (int u = 0; u < h; u++) {
            for (int d = u; d < h; d++) {
                vector<int> cnt(SIZE, 0);
                cnt[OFFSET] = 1;
                int s = 0;
                for (int j = 0; j < w; j++) {
                    int col_sum = pre[d + 1][j] - pre[u][j];
                    s += col_sum;
                    int idx = s + OFFSET;
                    ans += cnt[idx];
                    cnt[idx]++;
                }
            }
        }

        cout << ans << '\n';
    }

    return 0;
}

Submission Info

Judge Result