1.題目描述

給你一個二維字符矩陣?grid，其中?grid[i][j]?可能是?'X'、'Y'?或?'.'，返回滿足以下條件的子矩陣數量：

• 包含?grid[0][0]
• 'X'?和?'Y'?的頻數相等。
• 至少包含一個?'X'。

示例 1：

輸入：?grid = [["X","Y","."],["Y",".","."]]

輸出：?3

解釋：

示例 2：

輸入：?grid = [["X","X"],["X","Y"]]

輸出：?0

解釋：

不存在滿足?'X'?和?'Y'?頻數相等的子矩陣。

2.解題思路

拿到這題首先可以想到使用dp數組存儲以每一個點為結束位置的子矩陣中的X,Y個數，可以看出對于下標[i,j]，假設i,j均>=1,那么dp[i][j]對應矩陣的X，Y個數是可以通過dp[i-1][j],dp[i][j-1]以及dp[i-1][j-1]這三個子矩陣進行加減操作得到的。

因此，為了表示每個以i，j為結束位置的子矩陣中"X"和“Y”各自的個數，我們定義一個三維dp數組，dp[i][j][0]用于記錄"X"的個數，dp[i][j][1]用于記錄“Y”的個數，接下來只需要先初始化第0行和第0列這兩種特殊情況，然后一般情況就可以通過遞推式進行判斷

3.代碼實現

Java版

class Solution {public int numberOfSubmatrices(char[][] grid) {int m = grid.length, n = grid[0].length;int[][][] dp = new int[m][n][2];if (grid[0][0] == 'X') {dp[0][0][0] += 1;} else if (grid[0][0] == 'Y') {dp[0][0][1] += 1;}int ans = 0;//初始化第0行for (int j = 1; j < n; j++) {int x = dp[0][j-1][0];int y = dp[0][j-1][1];if (grid[0][j] == 'X') {x += 1;} else if (grid[0][j] == 'Y') {y += 1;}dp[0][j][0] = x;dp[0][j][1] = y;if (dp[0][j][0] >= 1 && dp[0][j][0] == dp[0][j][1]) {ans += 1;}}//初始化第0列for (int i = 1; i < m; i++) {int x = dp[i-1][0][0];int y = dp[i-1][0][1];if (grid[i][0] == 'X') {x += 1;} else if (grid[i][0] == 'Y') {y += 1;}dp[i][0][0] = x;dp[i][0][1] = y;if (dp[i][0][0] >= 1 && dp[i][0][0] == dp[i][0][1]) {ans += 1;}}//遍歷for (int i = 1; i < m; i++) {for (int j = 1; j < n; j++) {int x = dp[i-1][j][0] + dp[i][j-1][0] - dp[i-1][j-1][0];int y = dp[i-1][j][1] + dp[i][j-1][1] - dp[i-1][j-1][1];if (grid[i][j] == 'X') {x += 1;} else if (grid[i][j] == 'Y') {y += 1;}dp[i][j][0] = x;dp[i][j][1] = y;if (dp[i][j][0] >= 1 && dp[i][j][0] == dp[i][j][1]) {ans += 1;}}}return ans;}
}

Python版

class Solution:def numberOfSubmatrices(self, grid: List[List[str]]) -> int:m,n = len(grid),len(grid[0])ans = 0dp = [[[0,0] for _ in range(n)] for _ in range(m)]if grid[0][0] == 'X':dp[0][0] = [1,0]elif grid[0][0] == 'Y':dp[0][0] = [0,1]#初始化第0行for j in range(1,n):if grid[0][j] == 'X':dp[0][j] = [dp[0][j-1][0] + 1,dp[0][j-1][1]]elif grid[0][j] == 'Y':dp[0][j] = [dp[0][j-1][0],dp[0][j-1][1] + 1]else:dp[0][j] = dp[0][j-1] if dp[0][j][0] >= 1 and dp[0][j][0] == dp[0][j][1]:ans += 1#初始化第0列for i in range(1,m):if grid[i][0] == 'X':dp[i][0] = [dp[i-1][0][0] + 1,dp[i-1][0][1]]elif grid[i][0] == 'Y':dp[i][0] = [dp[i-1][0][0],dp[i-1][0][1] + 1]else:dp[i][0] = dp[i-1][0]if dp[i][0][0] >= 1 and dp[i][0][0] == dp[i][0][1]:ans += 1for i in range(1,m):for j in range(1,n):x = dp[i-1][j][0] + dp[i][j-1][0] - dp[i-1][j-1][0]y = dp[i-1][j][1] + dp[i][j-1][1] - dp[i-1][j-1][1]if grid[i][j] == 'X':dp[i][j] = [x+1,y]elif grid[i][j] == 'Y':dp[i][j] = [x,y+1]else:dp[i][j] = [x,y]if dp[i][j][0] >= 1 and dp[i][j][0] == dp[i][j][1]:ans += 1return ans