페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#5940

알록달록 미로 1초 1024MB

문제

n \times m개의 방으로 구성된 미로가 있다. 왼쪽 상단 방은 (1,1)로 표시되고, 오른쪽 하단 방은 (n,m)으로 표시된다.

인접한 방 사이에는 네 가지 색상 중 하나로 색칠된 문이 있는데, 각 색은 빨간색은 'C', 파란색은 'P', 초록색은 'Z', 주황색은 'N'으로 표시된다.

위 그림은 세 번째 예제의 그림으로, 세 번째 예제의 네 번째 질문인 "1 4 4 1"의 경우에서 (1,4)방에서 (4,1)방까지 가는 경로 상 세 가지 다른 색상의 문을 통과하는 경로 중 하나를 보여주고 있다.

시작 방과 도착 방의 좌표가 질문으로 주어졌을 때, 시작 방에서 출발하여 도착 방까지 가는 경로에서 거쳐야 하는 문의 색상의 최소 수는 몇인지 알아보자.


입력

첫 줄에는 방의 수인 정수 n과 m이 주어진다. (1 ≤ n, m ≤ 100, 1 < n × m)

다음 n 줄 중 i 번째에는 m − 1개의 문자('P', 'C', 'Z' 또는 'N')로 이루어진 문자열이 주어지며, j 번째 문자는 (i, j)방과 (i, j + 1)방을 연결하는 문의 색을 의미한다.

다음 n − 1 줄 중 i 번째에는 m 개의 문자('P', 'C', 'Z' 또는 'N')로 이루어진 문자열이 주어지며, j 번째 문자는 (i, j)방과 (i + 1, j)방을 연결하는 문의 색을 의미한다.

다음 줄에는 질문 수인 정수 q가 주어진다. (1 ≤ q ≤ 100)

다음 q 줄의 i번째 줄에는 i번째 질문을 설명하는 4개의 정수 a_i , b_i , c_i , d_i (1 ≤ a_i , c_i ≤ n, 1 ≤ b_i , d_i ≤ m, (ai, bi) ≠ (ci, di))


출력

q줄에 걸쳐 i번째 줄에 i번째 질문의 답을 출력한다.


부분문제

번호 점수 조건
#116점

n=1

#219점

방 (i, j)와 (i, j + 1)을 연결하는 문은 모두 파란색이고, 방 (i, j)와 (i + 1, j)를 연결하는 모든 문은 빨간색입니다.

#334점

모든 문은 빨간색이거나 파란색입니다.

#431점

추가 제한 없음


예제1

입력
18
CPZNCCP
4
1118
1315
1814
1213
출력
4
2
3
1

예제2

입력
33
PP
PP
PP
CCC
CCC
3
1133
3322
1113
출력
2
2
1

예제3

입력
44
CCC
CPC
PPP
CNP
ZZZZ
PPPP
CPZC
4
3123
1144
2233
1441
출력
1
2
1
3

본문에 있는 이미지가 이 예제를 보여줍니다.

첫 번째 질문의 경우 Teo와 Gabriel은 파란색 문만 사용하여 나머지 팀원들에게 연락할 수 있습니다. 두 번째 질문에는 파란색과 녹색 문을 사용할 수 있습니다. 세 번째에는 파란색만으로 충분합니다. 네 번째로는 파란색, 녹색, 빨간색 문을 사용할 수 있습니다.


출처

COCI 2023/2024 Contest #1 2번

역링크