Placeholder

#5940

알록달록 미로 1초 1024MB

문제

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

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

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

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


입력

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

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

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

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

다음 qq 줄의 ii번째 줄에는 ii번째 질문을 설명하는 44개의 정수 ai,bi,ci,dia_i , b_i , c_i , d_i (1≤ai,ci≤n1 ≤ a_i , c_i ≤ n, 1≤bi,di≤m1 ≤ b_i , d_i ≤ m, (ai,bi)≠(ci,di)(ai, bi) ≠ (ci, di))


출력

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


부분문제

번호 점수 조건
#116점

n=1n=1

#219점

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

#334점

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

#431점

추가 제한 없음


예제1

입력
1 8
CPZNCCP
4
1 1 1 8
1 3 1 5
1 8 1 4
1 2 1 3
출력
4
2
3
1

예제2

입력
3 3
PP
PP
PP
CCC
CCC
3
1 1 3 3
3 3 2 2
1 1 1 3
출력
2
2
1

예제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
출력
1
2
1
3

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

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


출처

COCI 2023/2024 Contest #1 2번


역링크 공식 문제집만

로그인해야 코드를 작성할 수 있어요.
알록달록 미로 - JUNGOL