Submission #66776482

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
    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)
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
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
    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){
            vector<string> t(w,string(h,' '));
            for(int i=0;i<h;i++) for(int j=0;j<w;j++) t[j][i]=grid[i][j];
            grid.swap(t);
            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));
        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);
                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