K-Square Game_2026牛客五一集训派对day2

时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

Have you ever heard of the game Hex? Hex is a two-player game played on a hexagonal board. The rules are that the red/blue players take turns placing their colored pieces on empty spaces on the board until the red player connects the top and bottom of the board or the blue player connects the left and right of the board. The first player to achieve their goal wins. Here the connection condition is that there must be a path of the player's color connecting two adjacent hexagons with at least one common edge. For example, the following two Hex game boards are both victories for the blue player.

It can be proven that there is only one winning player in Hex.

Bobo also wants to play Hex, but he thinks that having hexagonal cells on the board is too complicated. So, he invented a new game called Square! The rules of Square are similar to Hex, where the red/blue players take turns placing their colored pieces on empty spaces on the board until the red player connects the top and bottom of the board or the blue player connects the left and right of the board. However, in Square, the board is a rectangle made up of many small squares, and the connection condition remains the same, which is to have a path of the player's color connecting two adjacent squares with at least one common edge (i.e., four-connected). The following two Square boards on a $5 \times 6$ board are victories for the red and blue players, respectively.

Bobo was excited to share this Square game with his friend, oboB. However, oboB immediately realized a problem: Bobo's Square game may result in a tie! For example, the following two Square game boards on a $5 \times 6$ board are both ties because both players have no moves left, and the red pieces are not connected to the top and bottom of the board, and the blue pieces are not connected to the left and right of the board.

"But...there shouldn't be many tie games, right?" Bobo said stubbornly. To refute Bobo, oboB drew a $n$ -row by $m$ -column matrix of red and blue cells. "I randomly select a submatrix from here as the game board, and there is a high probability that it will be a tie!" Bobo seemed to agree, but he suddenly thought of something else, "In order to make the rules of Square valid, the submatrix selected must have all red cells at the top and bottom and all blue cells on the left and right! (corresponding to the red/blue lines in the example matrix)" oboB had no choice but to agree with Bobo's argument, "Then could you please count how many game boards satisfy this condition?"

Formally, given an $n$ -row by $m$ -column matrix $A$ , where each cell is either red ('R') or blue ('B'), you need to count the number of quadruples $(x_1, x_2, y_1, y_2)$ satisfying the following conditions (where $(x_1, y_1)$ and $(x_2, y_2)$ are the coordinates of the top-left and bottom-right corners of the submatrix you select):

1. $2 \leq x_1 \leq x_2 \leq n-1$ , $2 \leq y_1 \leq y_2 \leq m-1$ (you must select a submatrix)
2. $\forall y_1 \leq j \leq y_2$ , $A_{x_1-1,j}=A_{x_2+1,j}=$ 'R' (the top and bottom of the submatrix must be all red)
3. $\forall x_1 \leq i \leq x_2$ , $A_{i,y_1-1}=A_{i,y_2+1}=$ 'B' (the left and right of the submatrix must be all blue)
4. There does not exist a sequence of cells $P=((i_1,j_1),(i_2,j_2),\dots,(i_{\ell},j_{\ell}))$ satisfying:
     (a) $\ell \geq 1$ , $i_1=x_1$ , $i_\ell=x_2$
(b) $\forall 1\leq k\leq \ell$ , $x_1\leq i_k\leq x_2 \land y_1\leq j_k\leq y_2$
(c) $\forall 1\leq k\leq \ell$ , $A_{i_k,j_k}=$ 'R'
     (d) $\forall 1\leq k\leq \ell-1$ , $|i_k-i_{k+1}|+|j_k-j_{k+1}|=1$
    (there is no connected submatrix with a red path between the top and the bottom)

5. There does not exist a sequence of cells $P=((i_1,j_1),(i_2,j_2),\dots,(i_{\ell},j_{\ell}))$ satisfying:

(a) $\ell \geq 1$ , $j_1=y_1$ , $j_\ell=y_2$

(b) $\forall 1\leq k\leq \ell$ , $x_1\leq i_k\leq x_2 \land y_1\leq j_k\leq y_2$
(c) $\forall 1\leq k\leq \ell$ , $A_{i_k,j_k}=$ 'B'
(d) $\forall 1\leq k\leq \ell-1$ , $|i_k-i_{k+1}|+|j_k-j_{k+1}|=1$
(there is no connected submatrix with a blue path between the left and the right)

输入描述:

The first line contains two integers  and  , denoting the number of rows and columns of the matrix, respectively.
In the following  lines, the -th  line contains a string of length , consisting only of 'R' and 'B'. The -th  character in the -th line denotes the color of the cell in the -th row and -th column of the matrix, where 'R' stands for red and 'B' stands for blue.

输出描述:

Output an integer in a line, denoting the number of submatrices that form a tie in a Square board (the formal definition has already been given in the problem statement).

示例1

输入

复制

6 6
RRRRRB
BRRRBB
BBRBBB
BBBRBB
BBRRRB
BRRRRR

输出

复制

示例2

输入

复制

5 5
BRRRB
BBRRB
BRBRB
BRRBB
BRRRB

输出

复制

示例3

输入

复制

7 7
BRRRRRB
BRBBBRB
BBRBRBB
BRRRRRB
BBRBRBB
BRBBBRB
BRRRRRB

输出

复制

示例4

输入

复制

3 3
RRR
BRB
RRR

输出

复制

示例5

输入

复制

20 20
RRRRRRRRRRRRRRRRRRRR
BRRRRRRRRRRRRRRRRRRB
BBBBBBRRBBBBRRRRRRRB
BRRRRBBBBRRBRRRRRRRB
BRRRRRRRRRRBRRRRRRRB
BBBBBBBBBBBBRRRRRRRB
BRRRRRRRRRRRRRRRRRRB
BRRRRRRRRRRRRRRRRRRB
BBBBBBBBBRRRRRRRRRRB
BRRRRRRRBRBBBBRRRRRB
BRRRRRRRBBBRRBRRRRRB
BRRRRRRRRRRRRBRRRBBB
BRRRRRRRRRRRRBRBBBRB
BBBBBBBRRRRRRBBBRRRB
BRRRRRBRRRRRRRRRRRRB
BRRRRRBRRRRRRRRRRRRB
BRRRRRBRRRRRRRRRRRRB
BBBBBBBBBBRRRRRRRRRB
BRRRRRRRRRRRRRRRRRRB
RRRRRRRRRRRRRRRRRRRR

输出

复制

备注:

To aid understanding, we provide graphical illustrations for the first two sample tests. The two valid submatrices in the first sample test are shown below.






One valid submatrix in the second sample test is shown below.