Have you ever heard of the game Hex? Hex is a two-pla
yer 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×65 \times 65×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×65 \times 65×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 nnn-row by mmm-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 nnn-row by mmm-column matrix AAA, where each cell is either red ('R') or blue ('B'), you need to count the number of quadruples (x1,x2,y1,y2)(x_1, x_2, y_1, y_2)(x1,x2,y1,y2) satisfying the following conditions (where (x1,y1)(x_1, y_1)(x1,y1) and (x2,y2)(x_2, y_2)(x2,y2) are the coordinates of the top-left and bottom-right corners of the submatrix you select):
1. 2≤x1≤x2≤n−12 \leq x_1 \leq x_2 \leq n-12≤x1≤x2≤n−1, 2≤y1≤y2≤m−12 \leq y_1 \leq y_2 \leq m-12≤y1≤y2≤m−1 (you must select a submatrix)
2. ∀y1≤j≤y2\forall y_1 \leq j \leq y_2∀y1≤j≤y2, Ax1−1,j=Ax2+1,j=A_{x_1-1,j}=A_{x_2+1,j}=Ax1−1,j=Ax2+1,j='R' (the top and bottom of the submatrix must be all red)
3. ∀x1≤i≤x2\forall x_1 \leq i \leq x_2∀x1≤i≤x2, Ai,y1−1=Ai,y2+1=A_{i,y_1-1}=A_{i,y_2+1}=Ai,y1−1=Ai,y2+1='B' (the left and right of the submatrix must be all blue)
4. There does not exist a sequence of cells P=((i1,j1),(i2,j2),…,(iℓ,jℓ))P=((i_1,j_1),(i_2,j_2),\dots,(i_{\ell},j_{\ell}))P=((i1,j1),(i2,j2),…,(iℓ,jℓ)) satisfying:
(a) ℓ≥1\ell \geq 1ℓ≥1, i1=x1i_1=x_1i1=x1, iℓ=x2i_\ell=x_2iℓ=x2
(b) ∀1≤k≤ℓ\forall 1\leq k\leq \ell∀1≤k≤ℓ, x1≤ik≤x2∧y1≤jk≤y2x_1\leq i_k\leq x_2 \land y_1\leq j_k\leq y_2x1≤ik≤x2∧y1≤jk≤y2
(c) ∀1≤k≤ℓ\forall 1\leq k\leq \ell∀1≤k≤ℓ, Aik,jk=A_{i_k,j_k}=Aik,jk='R'
(d) ∀1≤k≤ℓ−1\forall 1\leq k\leq \ell-1∀1≤k≤ℓ−1, ∣ik−ik+1∣+∣jk−jk+1∣=1|i_k-i_{k+1}|+|j_k-j_{k+1}|=1∣ik−ik+1∣+∣jk−jk+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=((i1,j1),(i2,j2),…,(iℓ,jℓ))P=((i_1,j_1),(i_2,j_2),\dots,(i_{\ell},j_{\ell}))P=((i1,j1),(i2,j2),…,(iℓ,jℓ)) satisfying:
(a) ℓ≥1\ell \geq 1ℓ≥1, j1=y1j_1=y_1j1=y1, jℓ=y2j_\ell=y_2jℓ=y2
(b) ∀1≤k≤ℓ\forall 1\leq k\leq \ell∀1≤k≤ℓ, x1≤ik≤x2∧y1≤jk≤y2x_1\leq i_k\leq x_2 \land y_1\leq j_k\leq y_2x1≤ik≤x2∧y1≤jk≤y2
(c) ∀1≤k≤ℓ\forall 1\leq k\leq \ell∀1≤k≤ℓ, Aik,jk=A_{i_k,j_k}=Aik,jk='B'
(d) ∀1≤k≤ℓ−1\forall 1\leq k\leq \ell-1∀1≤k≤ℓ−1, ∣ik−ik+1∣+∣jk−jk+1∣=1|i_k-i_{k+1}|+|j_k-j_{k+1}|=1∣ik−ik+1∣+∣jk−jk+1∣=1
(there is no connected submatrix with a blue path between the left and the right)