Labirint
레이팅 미적용의견: 0
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\) rooms, all of the
same size. The rooms form a grid. The t\(op-le\)ft room is labeled with (1, 1), and
the bott\(om-ri\)ght with (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
\(at\) \(in\) the fourth question, and the white circle marks the room \(in\) which Vito, Ivo and Dino are located at.
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@@RISE_MATH_BLOCK_0@@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\) of Gabriel’s questions!
Subtask 1 (11 points): \(n = 1\)
Subtask 2 (13 points): All doors that connect rooms (\(i\), \(j\)) with (\(i\), \(j + 1\)) are blue, and all doors that connect rooms (\(i\), \(j\)) with (\(i + 1\), \(j\)) are red.
Subtask 3 (24 points): Every door is either red or blue.
Subtask 4 (22 points): No additional constraints.
The first line contains integers \(n\) and \(m\) (\(1 \le n\), \(m \le 100\), \(1 < n \times m\)), the number of rooms.
The \(i-th\) of the following \(n\) lines contains \(m - 1\) characters (’P’, ’C’, ’Z’ or ’N’), where the \(j-th\) character
marks the colour of the door that connects rooms (\(i\), \(j\)) and (\(i\), \(j + 1\)).
The \(i-th\) of the following \(n - 1\) lines contains \(m\) characters (’P’, ’C’, ’Z’ or ’N’), where the \(j-th\) character
marks the colour of the door that connects rooms (\(i\), \(j\)) and (\(i + 1\), \(j\)).
The next line contains the integer \(q\) (\(1 \le q \le 100\)), the number of Gabriel’s questions.
In the \(i-th\) of the following \(q\) lines, there are four integers \(a@@RISE_MATH_BLOCK_0@@i\), \(c@@RISE_MATH_BLOCK_1@@i\) (\(1 \le a@@RISE_MATH_BLOCK_2@@i\), d\(i \le m\),
(\(a_{i}\), b_{i})̸ = (\(c_{i}\), d_{i})), the description of Gabriel’s \(i-th\) question.
In the \(i-th\) of \(q\) lines, output the answer to Gabriel’s \(i-th\) question.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 11점 | \(n = 1\) |
2 | 13점 | All doors that connect rooms (\(i\), \(j\)) with (\(i\), \(j + 1\)) are blue, and all doors that connect rooms (\(i\), \(j\)) with (\(i + 1\), \(j\)) are red. |
3 | 24점 | Every door is either red or blue. |
4 | 22점 | No additional constraints. |
1 8
CPZNCCP
4
1 1 1 8
1 3 1 5
1 8 1 4
1 2 1 34
2
3
13 3
PP
PP
PP
CCC
CCC
3
1 1 3 3
3 3 2 2
1 1 1 32
2
14 4
CCC
CPC
PPP
CNP
ZZZZ
PPPP
CPZC
4
3 1 2 3
1 1 4 4
2 2 3 3
1 4 4 11
2
1
3Clarification of the third example:
The third example is illustrated in the text.
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.
평가 및 의견
Labirint
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Labirint