Steward

分享是一種喜悅、更是一種幸福

程式語言 - LeetCode - C - 3212. Count Submatrices With Equal Frequency of X and Y

---

參考資訊：
https://algo.monster/liteproblems/3212

題目：


方法：

Dynamic Programming

解答：

int numberOfSubmatrices(char** grid, int gridSize, int* gridColSize)
{
    int r = 0;
    int i = 0;
    int j = 0;
    int row_size = gridSize;
    int col_size = gridColSize[0];
    int** sx = calloc(row_size + 1, sizeof(int *));
    int** sy = calloc(row_size + 1, sizeof(int *));

    for (i = 0; i <= row_size; i++) {
        sx[i] = calloc(col_size + 1, sizeof(int));
        sy[i] = calloc(col_size + 1, sizeof(int));
    }

    for (i = 1; i <= row_size; i++) {
        for (j = 1; j <= col_size; j++) {
            sx[i][j] = sx[i - 1][j] + sx[i][j - 1];
            sx[i][j] -= sx[i - 1][j - 1];
            sx[i][j] += (grid[i - 1][j - 1] == 'X' ? 1 : 0);

            sy[i][j] = sy[i - 1][j] + sy[i][j - 1];
            sy[i][j] -= sy[i - 1][j - 1];
            sy[i][j] += (grid[i - 1][j - 1] == 'Y' ? 1 : 0); 

            if (sx[i][j] && (sx[i][j] == sy[i][j])) {
                r += 1;
            }
        }
    }

    return r;
}