<p>Given a 2D character matrix <code>grid</code>, where <code>grid[i][j]</code> is either <code>&#39;X&#39;</code>, <code>&#39;Y&#39;</code>, or <code>&#39;.&#39;</code>, return the number of <span data-keyword="submatrix">submatrices</span> that contain:</p>

<ul>
	<li><code>grid[0][0]</code></li>
	<li>an <strong>equal</strong> frequency of <code>&#39;X&#39;</code> and <code>&#39;Y&#39;</code>.</li>
	<li><strong>at least</strong> one <code>&#39;X&#39;</code>.</li>
</ul>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">grid = [[&quot;X&quot;,&quot;Y&quot;,&quot;.&quot;],[&quot;Y&quot;,&quot;.&quot;,&quot;.&quot;]]</span></p>

<p><strong>Output:</strong> <span class="example-io">3</span></p>

<p><strong>Explanation:</strong></p>

<p><strong><img alt="" src="https://assets.leetcode.com/uploads/2024/06/07/examplems.png" style="padding: 10px; background: rgb(255, 255, 255); border-radius: 0.5rem; width: 175px; height: 350px;" /></strong></p>
</div>

<p><strong class="example">Example 2:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">grid = [[&quot;X&quot;,&quot;X&quot;],[&quot;X&quot;,&quot;Y&quot;]]</span></p>

<p><strong>Output:</strong> <span class="example-io">0</span></p>

<p><strong>Explanation:</strong></p>

<p>No submatrix has an equal frequency of <code>&#39;X&#39;</code> and <code>&#39;Y&#39;</code>.</p>
</div>

<p><strong class="example">Example 3:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">grid = [[&quot;.&quot;,&quot;.&quot;],[&quot;.&quot;,&quot;.&quot;]]</span></p>

<p><strong>Output:</strong> <span class="example-io">0</span></p>

<p><strong>Explanation:</strong></p>

<p>No submatrix has at least one <code>&#39;X&#39;</code>.</p>
</div>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= grid.length, grid[i].length &lt;= 1000</code></li>
	<li><code>grid[i][j]</code> is either <code>&#39;X&#39;</code>, <code>&#39;Y&#39;</code>, or <code>&#39;.&#39;</code>.</li>
</ul>

class Solution:
    def numberOfSubmatrices(self, grid: List[List[str]]) -> int:
        ROW, COL=len(grid), len(grid[0])
        res=0
        diff=[[None] * COL for _ in range(ROW)]
        if grid[0][0]=='X':
            diff[0][0]=1
        if grid[0][0]=='Y':
            diff[0][0]=-1
        for i in range(1, COL):
            if grid[0][i]=='.':
                diff[0][i]=diff[0][i-1]
            else:
                diff[0][i]=(0 if diff[0][i-1] is None else diff[0][i-1])+(1 if grid[0][i]=='X' else -1)
            if diff[0][i]==0:
                res+=1
        for i in range(1, ROW):
            if grid[i][0]=='.':
                diff[i][0]=diff[i-1][0]
            else:
                diff[i][0]=(0 if diff[i-1][0] is None else diff[i-1][0]) + (1 if grid[i][0]=='X' else -1)
            if diff[i][0]==0:
                res+=1
        for r in range(1, ROW):
            for c in range(1, COL):
                v1, v2, v3=diff[r-1][c], diff[r][c-1], diff[r-1][c-1]
                if v1 is not None or v2 is not None or v3 is not None:
                    diff[r][c]=(0 if diff[r-1][c] is None else diff[r-1][c]) + (0 if diff[r][c-1] is None else diff[r][c-1]) - (0 if diff[r-1][c-1] is None else diff[r-1][c-1])
                    if grid[r][c]!='.':
                        diff[r][c]+=(1 if grid[r][c]=='X' else -1)
                else:
                    if grid[r][c]=='X':
                        diff[r][c]=1
                    if grid[r][c]=='Y':
                        diff[r][c]=-1
                if diff[r][c]==0:
                    res+=1
        return res
53080