P9904 [COCI 2023/2024 #1] Labirint

Teo and the Croatian EJOI team are inside a maze.

The maze is an $n \times m$ grid. The top-left cell is $(1,1)$, and the bottom-right cell is $(n,m)$. Between every pair of adjacent cells (4-neighborhood, i.e., adjacent up, down, left, right), there is a door. Doors have four colors: blue, red, green, and orange, represented by the characters `P`, `C`, `Z`, `N`, respectively. You can only move to other cells by passing through doors. Now Teo gives you $q$ queries. Each query provides $a,b,c,d$, asking you to find a path from $(a,b)$ to $(c,d)$ that minimizes the number of distinct door colors used along the path. You need to output this minimum number of colors.

The first line contains two integers $n, m$, representing the number of rows and columns of the grid. Next is a character matrix with $n$ rows and $m - 1$ columns. The character in row $i$, column $j$ represents the color of the door between $(i,j)$ and $(i,j+1)$. Next is a character matrix with $n - 1$ rows and $m$ columns. The character in row $i$, column $j$ represents the color of the door between $(i,j)$ and $(i+1,j)$. Next is one line with an integer $q$, representing the number of queries. Then follow $q$ lines. The $i$-th line contains four integers $a_i, b_i, c_i, d_i$, meaning the minimum number of distinct door colors on a path from $(a_i,b_i)$ to $(c_i,d_i)$.

Output $q$ lines, each containing one integer, which is the answer to the corresponding query.

### Sample Explanation #3 As shown in the figure.  - For the first query, you only need to pass through blue doors. - For the second query, you only need to pass through blue and green doors. - For the third query, you only need to pass through blue doors. - For the fourth query, following the path in the figure, you only need to pass through red, blue, and green doors. ### Constraints For $100\%$ of the testdata, $1 \le n,m,q \le 100$, $nm > 1$, $1 \le a_i,c_i \le n$, $1 \le b_i,d_i \le m$, $(a_i,b_i) \ne (c_i,d_i)$, and the character matrices consist only of the characters `P`, `C`, `Z`, `N`. **This problem uses bundled tests.** | Subtask | Special Property | Points | | :----------: | :----------: | :----------: | | $1$ | $n = 1$ | $11$ | | $2$ | The first character matrix contains only `P`, and the second character matrix contains only `C` | $13$ | | $3$ | All character matrices contain only `C` and `P` | $24$ | | $4$ | No special properties | $22$ | ### Notes The scoring of this problem follows the original COCI problem settings, with a full score of $70$. Translated from [COCI2023-2024](https://hsin.hr/coci/archive/2023_2024/) [CONTEST #1](https://hsin.hr/coci/archive/2023_2024/contest1_tasks.pdf) _**T2 Labirint**_. Translated by ChatGPT 5