COCI '23 Contest 1 #2 Labirint

Points: 10 (partial)

Time limit: 1.0s

Memory limit: 512M

Problem type

What is an EJOI for you?

Game room!

Teo is searching for the Croatian EJOI team! She has already found Gabriel, but is still looking for Vito, Dino, and Ivo.

Teo and the EJOI team are in a labyrinth consisting of $n \times m$ ~n \times m~ rooms, all the same size. The rooms form a grid. The top-left room is labeled with $(1, 1)$ ~(1, 1)~, and the bottom-right with $(n, m)$ ~(n, m)~. Between each pair of adjacent rooms, there is a door colored in one of four colors: blue (marked with P), red (marked with C), green (marked with Z) and orange (marked with N).

Illustration of the third example. The black circle marks the room in which Teo and Gabriel are located in the fourth question, and the white circle marks the room in which Vito, Ivo and Dino are located. The gray path is one of the possible paths that passes through three different door colors.

At some point, Gabriel says:

I know where the rest of the team is, but I will only tell you if you can answer all of my questions.

Gabriel's questions are:

If we are currently in room $(a_i, b_i)$ ~(a_i, b_i)~ and the rest of the team is in room $(c_i, d_i)$ ~(c_i, d_i)~, what is the minimum number of door colors we have to go through to reach them?

Teo is very good at answering Gabriel's questions, but there are simply too many of them. She does not have much time (the bus is leaving soon), so she is asking you to help her answer $q$ ~q~ of Gabriel's questions!

Input Specification

The first line contains integers $n$ ~n~ and $m$ ~m~ $(1 \le n, m \le 100, 1 < n \times m)$ ~(1 \le n, m \le 100, 1 < n \times m)~, the number of rooms.

The $i$ ~i~-th of the following $n$ ~n~ lines contains $m-1$ ~m-1~ characters (P, C, Z or N), where the $j$ ~j~-th character marks the colour of the door that connects rooms $(i, j)$ ~(i, j)~ and ( $i, j + 1)$ ~i, j + 1)~.

The $i$ ~i~-th of the following $n-1$ ~n-1~ lines contains $m$ ~m~ characters (P, C, Z or N), where the $j$ ~j~-th character marks the colour of the door that connects rooms $(i, j)$ ~(i, j)~ and $(i + 1, j)$ ~(i + 1, j)~.

The next line contains the integer $q$ ~q~ $(1 \le q \le 100)$ ~(1 \le q \le 100)~, the number of Gabriel's questions.

In the $i$ ~i~-th of the following $q$ ~q~ lines, there are four integers $a_i$ ~a_i~, $b_i$ ~b_i~, $c_i$ ~c_i~, $d_i$ ~d_i~ $(1 \le a_i, c_i \le n, 1 \le b_i, d_i \le m, (a_i, b_i) \neq (c_i, d_i))$ , the description of Gabriel's $i$ ~i~-th question.

Output Specification

In the $i$ ~i~-th of $q$ ~q~ lines, output the answer to Gabriel's $i$ ~i~-th question.

Constraints

Subtask	Points	Constraints
1	11	$n = 1$ ~n = 1~
2	13	All doors that connect rooms $(i, j)$ ~(i, j)~ with $(i, j + 1)$ ~(i, j + 1)~ are blue, and all doors that connect rooms $(i, j)$ ~(i, j)~ with $(i + 1, j)$ ~(i + 1, j)~ are red.
3	24	Every door is either red or blue.
4	22	No additional constraints.

Sample Input 1

Sample Output 1

Sample Input 2

3 3
PP
PP
PP
CCC
CCC
3
1 1 3 3
3 3 2 2
1 1 1 3

Sample Output 2

2
2
1

Sample Input 3

4 4
CCC
CPC
PPP
CNP
ZZZZ
PPPP
CPZC
4
3 1 2 3
1 1 4 4
2 2 3 3
1 4 4 1

Sample Output 3

Explanation for Sample 3

The third example is illustrated in the problem statement.

For the first question, Teo and Gabriel can use just the blue doors to reach the rest of the team; for the second question, they can use blue and green doors; for the third, again, only blue is enough; and for the fourth, they can use blue, green, and red doors.

Comments

There are no comments at the moment.