P16439 [XJTUPC 2026] Bright / Grid

Y2hlOTYw is a chess lover. However, he does not have his own chessboard. One day, he got a piece of black-and-white grid paper with $n$ rows and $m$ columns. Of course, this is not a standard chessboard, but Y2hlOTYw does not care. He thinks that if every connected component formed by cells of the same color via 4-directional adjacency (up, down, left, right) has a rectangular shape, then this grid paper can be used as a chessboard. Now Y2hlOTYw wants you to help determine whether this grid paper can be used as a chessboard. Formally, let the grid paper be $G = \{(i, j) \mid 1 \le i \le n,\ 1 \le j \le m\}$, where $n$ and $m$ are positive integers. Each cell $(i,j)$ is assigned a color $\text{color}(i,j) \in \{\text{black},\text{white}\}$. Two cells $(i,j)$ and $(i',j')$ are adjacent if and only if $|i-i'| + |j-j'| = 1$. For a fixed color $c \in \{\text{black},\text{white}\}$, consider the subset $S_c = \{(i,j)\in G \mid \text{color}(i,j) = c\}$. Define an equivalence relation on $S_c$: two cells are equivalent if and only if there exists a sequence of cells $(i_1,j_1), (i_2,j_2), \dots, (i_k,j_k)$ such that every cell belongs to $S_c$, and for any $t$ ($1\le t\le k-1$), cell $(i_t,j_t)$ is adjacent to cell $(i_{t+1},j_{t+1})$. Each equivalence class is called a **connected component**. A connected component is maximal, i.e., it cannot be expanded by adding any adjacent cell of the same color. The shape of a set of cells $R \subseteq G$ is called a **rectangle** if there exist integers $r_1 \le r_2$ and $c_1 \le c_2$ such that: $$R = \{(i,j) \mid r_1 \le i \le r_2,\ c_1 \le j \le c_2\}$$ Now you need to determine whether the shape of every connected component is a rectangle.

**This problem contains multiple test cases**. The first line of the input contains a positive integer $T$ ($1\le T\le 8266$), indicating the number of test cases. Next are the descriptions of the $T$ test cases. The first line of each test case contains two integers $n$ and $m$ ($1 \le n,m \le 500$), separated by a space, indicating that the grid paper has $n$ rows and $m$ columns. The next $n$ lines: the $i$-th line contains a string $S_i$ of length exactly $m$, describing the given grid paper. It is guaranteed that $S_i$ contains only characters $\texttt{0}$ and $\texttt{1}$. For any integers $i$ and $j$ ($1\le i\le n, 1 \le j \le m$): - If the $j$-th character of the $i$-th line is $\texttt{1}$, then the cell $(i,j)$ in row $i$ and column $j$ is black ($\text{black}$). - If the $j$-th character of the $i$-th line is $\texttt{0}$, then the cell $(i,j)$ in row $i$ and column $j$ is white ($\text{white}$). It is guaranteed that the sum of $n \cdot m$ over all test cases does not exceed $2.5 \times 10^5$.

For each test case, output one line containing a string: - If this grid paper can be used as a chessboard, i.e., the shape of every connected component is a rectangle, output $\tt{Yes}$. - Otherwise, output $\tt{No}$. The answer is case-insensitive. For example, $\tt{yEs}$, $\tt{Yes}$, $\tt{yes}$, and $\tt{YES}$ will all be considered as $\tt{Yes}$.

Translated by ChatGPT 5