P7963 [NOIP2021] Chessboard

After losing at mahjong for a whole night, Xiao z and Xiao c uninstalled all card games on their phones. But how could that stop their determination to slack off in class? Now they set their eyes on board games, yet aside from playing Aeroplane Chess every day, they only know the rough rules of almost all other board games. “Since we both can play but only a little, why don’t we make our own mash-up?” So, with their wild imagination, a wonderful game that mixes Go, Chinese Chess, and Junqi (junqi, i.e., Chinese Army Chess) was born.

The game is played on a grid-shaped board with $n$ rows and $m$ columns. Pieces are placed on the intersections of the grid lines. We denote the top-left intersection as $(1,1)$ and the bottom-right intersection as $(n,m)$. Pieces come in two colors, black and white, and each player uses one color. Besides color, each piece also has a level. Let $\mathit{col}_i$ be the color of piece $i$, and $\mathit{lv}_i$ be the level of piece $i$. In addition, each grid edge on the board has one of $4$ states. For the $i$-th grid edge, let its state be $\mathit{opt}_i$. On a player’s turn, they may choose one of their own pieces and move it along grid edges to another intersection; this is called a move. Formally, a move is defined as choosing a coordinate sequence $(x_0,y_0),(x_1,y_1),\ldots,(x_k,y_k)$, where $k$ is any chosen positive integer, $(x_0,y_0)$ is the piece’s starting position, and $(x_k,y_k)$ is the final position. It must satisfy: - For any $i=0,1,\ldots,k-1$, the intersections $(x_i,y_i)$ and $(x_{i+1},y_{i+1})$ must be directly connected by a grid edge; that is, **the move must follow grid edges**. - For any $i\not=j$, we must have $(x_i,y_i)\ne(x_j,y_j)$; that is, no position may be visited twice during the move. In particular, $(x_0,y_0)\ne(x_k,y_k)$, meaning **the piece cannot stay in place (or return to its starting point)**. - For any $i=1,\ldots,k-1$, there must be no piece on $(x_i,y_i)$; that is, **the piece cannot pass through existing pieces**. - If there is no piece on $(x_k,y_k)$, it is a normal move; otherwise it is a capture. During a capture, let the moving piece have color $\mathit{col}_1$ and level $\mathit{lv}_1$, and the captured piece have color $\mathit{col}_2$ and level $\mathit{lv}_2$. Then it must hold that $\mathit{col}_1\ne\mathit{col}_2,\mathit{lv}_1\geq\mathit{lv}_2$. In other words, **you may only capture a piece of a different color whose level is not higher than yours**. Note that from the definition above, a piece is not allowed to keep moving forward after capturing. The meanings of grid edge states are as follows: - If $\mathit{opt}_i=0$, it means the road is blocked, and the move cannot pass through this grid edge. - If $\mathit{opt}_i=1$, it means the grid edge is a “normal road”. In each move, a piece may pass through at most $1$ normal road. - If $\mathit{opt}_i=2$, it means the grid edge is a “straight road”. In each move, a piece may pass through any number of straight roads, but it must **keep moving only horizontally or only vertically, and cannot turn**. For example, going from $(1,1)$ to $(1,3)$ via $(1,2)$ along straight roads is allowed, but going from $(1,1)$ to $(2,2)$ via $(1,2)$ is not. - If $\mathit{opt}_i=3$, it means the grid edge is a “connected road”. In each move, a piece may pass through any number of connected roads, and may turn freely along the way. It is also required that within a single move, **all grid edges passed through must have the same state**. For example, moving from $(1,1)$ to $(1,2)$ via a straight road and then from $(1,2)$ to $(1,3)$ via a connected road is not allowed. Other details such as how to decide the winner are irrelevant to this problem and are omitted. After developing this board game, Xiao z and Xiao c came up with a training strategy to improve: the board starts empty, and then Xiao c places one piece onto some empty intersection each time. Xiao z needs to quickly compute: if we choose this newly placed piece to make exactly one move, how many positions on the board can it reach in total? Note that since this is only mental training, they will not actually move the piece. Poor Xiao z found his computing ability is not enough to solve this, so he asks you for help.

Each test contains multiple test cases. The first line contains a positive integer $T$, the number of test cases. For each test case: The first line contains three positive integers $n, m, q$, representing the number of rows, columns, and the number of turns. The next $n$ lines each contain a string of length $m - 1$, consisting of characters $\texttt{0}$, $\texttt{1}$, $\texttt{2}$, $\texttt{3}$. The $j$-th character in the $i$-th line represents the state of the grid edge connecting intersection $(i, j)$ to intersection $(i, j + 1)$. The next $n - 1$ lines each contain a string of length $m$, consisting of characters $\texttt{0}$, $\texttt{1}$, $\texttt{2}$, $\texttt{3}$. The $j$-th character in the $i$-th line represents the state of the grid edge connecting intersection $(i, j)$ to intersection $(i + 1, j)$. The next $q$ lines each contain $4$ non-negative integers $\mathit{col}_i , \mathit{lv}_i , x_i , y_i$, meaning that in turn $i$, a piece with color $\mathit{col}_i$ and level $\mathit{lv}_i$ is placed at intersection $(x_i , y_i)$. Here $\mathit{col}_i = 0$ denotes a black piece, and $\mathit{col}_i = 1$ denotes a white piece. It is guaranteed that there was no piece on $(x_i , y_i)$ before.

For each test case, output $q$ lines. Each line contains a non-negative integer, representing the number of intersections that the $i$-th newly placed piece can reach after it is placed.

**[Sample Explanation #1]** After placing piece $1$, the positions it can reach are $(2, 1),(2, 2),(3, 2),(3, 3)$. After placing piece $2$, the positions it can reach are $(2, 2),(2, 3),(3, 1)$. After placing piece $3$, the positions it can reach are $(1, 1),(1, 3),(2, 2)$. After placing piece $4$, the positions it can reach are $(2, 2),(3, 1),(3, 3)$. After placing piece $5$, the positions it can reach are $(2, 3),(3, 2)$. **[Constraints]** | Test Point ID | $n \times m \le$ | $q \le$ | Special Property | |:-:|:-:|:-:|:-:| | $1 \sim 2$ | $100$ | $50$ | None | | $3 \sim 6$ | $5000$ | $2000$ | None | | $7 \sim 8$ | $2 \times {10}^5$ | ${10}^5$ | No “straight roads” and no “connected roads” | | $9 \sim 11$ | $2 \times {10}^5$ | ${10}^5$ | No “connected roads” | | $12 \sim 14$ | $2 \times {10}^5$ | ${10}^5$ | No “straight roads” | | $15 \sim 16$ | $2 \times {10}^5$ | ${10}^5$ | $\mathit{lv}_i = i$ | | $17 \sim 18$ | $2 \times {10}^5$ | ${10}^5$ | $\mathit{lv}_i = q - i + 1$ | | $19 \sim 21$ | $2 \times {10}^5$ | $2000$ | $n, m \le 1000$ | | $22 \sim 25$ | $2 \times {10}^5$ | ${10}^5$ | None | For $100\%$ of the testdata, $1 \le T \le 5$, $2 \le n, m \le {10}^5$, $4 \le n \times m \le 2 \times {10}^5$, $1 \le q \le \min \{ {10}^5, n \times m \}$, $1 \le \mathit{lv}_i \le q$, $1 \le x_i \le n$, $1 \le y_i \le m$, $\mathit{col}_i \in \{ 0, 1 \}$. Note: Since the input and output size of this problem is large, it is recommended to use faster I/O methods. Translated by ChatGPT 5