详见代码说明

// Google Kickstart2021 Round A Problem B: L形图
/*
核心思路是: 
    枚举矩阵中的每一个点，计算一下如果把当前这个点作为'L'中两线段的交点
    能组成多少个'L'形

时间复杂度: O(r*c)
*/

#include <cstring>
#include <iostream>

using namespace std;

const int N = 1010;

int r, c; // row, column  r行c列
int g[N][N]; // g用来存原单元格矩阵
int U[N][N], D[N][N], L[N][N], R[N][N]; // up, down, left, right
// U, D, L, R 分别记录在第(i, j)个格子中, 上/下/左/右边能到达的最大长度

// 给定当前点的上下左右最大长度，计算以该点为交点能组成多少个'L'形
int cal(int u, int d, int l, int r) {
    int res = 0;
    if (u >= 4) // 只有当上边长度超过4，才可以把上边当作'L'的长边，以下同理
        res += min(u >> 1, l) + min(u >> 1, r) - 2;
    if (d >= 4)
        res += min(d >> 1, l) + min(d >> 1, r) - 2;
    if (l >= 4) 
        res += min(l >> 1, u) + min(l >> 1, d) - 2;
    if (r >= 4) 
        res += min(r >> 1, u) + min(r >> 1, d) - 2;
    /*
    如果看不懂上面的计算，可以先看看我原来的代码
    实际上只是做了一个代码等价变形而已
    if (u >= 4) {
        if (l >= u >> 1) res += u / 2 - 1;
        else res += l - 1;
        if (r >= u >> 1) res += u / 2 - 1;
        else res += r - 1;
    }
    ...
    */
    return res;
}

int main() {
    int T;
    scanf("%d", &T);
    for (int C = 1; C <= T; C ++ ) {
        memset(U, 0, sizeof U);
        memset(D, 0, sizeof D);
        memset(L, 0, sizeof L);
        memset(R, 0, sizeof R);

        scanf("%d%d", &r, &c);
        for (int i = 1; i <= r; i ++ ) 
            for (int j = 1; j <= c; j ++ ) 
                scanf("%d", &g[i][j]);

        // 计算每一个点的上/下/左/右边能到达的最大长度
        for (int i = 1; i <= r; i ++ ) 
            for (int j = 1; j <= c; j ++ )
                if (g[i][j]) {
                    U[i][j] = U[i - 1][j] + 1;
                    L[i][j] = L[i][j - 1] + 1;
                }
        for (int i = r; i; i -- )
            for (int j = c; j; j -- ) 
                if (g[i][j]) {
                    D[i][j] = D[i + 1][j] + 1;
                    R[i][j] = R[i][j + 1] + 1;
                }

        // 结果可能爆int所以用long long来存
        long long res = 0;
        for (int i = 1; i <= r; i ++ )
            for (int j = 1; j <= c; j ++ ) 
                if (g[i][j]) // 只有当g[i][j]是1的时候才能作为交点
                    res += cal(U[i][j], D[i][j], L[i][j], R[i][j]);

        printf("Case #%d: %lld\n", C, res);
    }
}