Mê cung

Time limit: 1.0s , Memory limit: 256M , Points: 1

Hình ảnh tạo bởi ChatGPT

Alan và nhóm bạn đang tìm cách thoát khỏi một mê cung có dạng ma trận lưới kích thước $n × m$, mỗi ô vuông đại diện cho một căn phòng. Các ô vuông được đánh số từ $1$ ~1~ đến $n$ ~n~ từ trên xuống dưới và từ $1$ ~1~ đến $m$ ~m~ từ trái sang phải. Giữa hai căn phòng liền kề đều có một cánh cửa được ký hiệu bởi một trong bốn màu: lam (ký hiệu chữ $P$ ~P~), đỏ (ký hiệu chữ $C$ ~C~), lục (ký hiệu chữ $Z$ ~Z~) và cam (ký hiệu chữ $N$ ~N~). Alan và nhóm bạn có thể di chuyển giữa hai căn phòng liền kề bất kỳ thông qua cánh cửa.

Alan đặt ra câu hỏi rằng nếu vị trí hiện tại của nhóm đang ở phòng $(a_i,b_i)$ ~(a_i,b_i)~ và lối thoát nằm ở phòng $(c_i,d_i)$ ~(c_i,d_i)~, đường đi nào sẽ đi qua ít màu cửa nhất để đến với lối thoát.

Bạn hãy giúp Alan trả lời tổng cộng $q$ ~q~ câu hỏi, mỗi câu hỏi yêu cầu tìm một đường đi băng qua các cánh cửa giữa các phòng để đến lối thoát, sao cho tổng số lượng màu cửa đã đi qua là ít nhất có thể.

Input

Dòng đầu tiên chứa hai số nguyên $n$ ~n~ và $m$ ~m~ $(1 \le n,m \le 100; 1 < n×m)$.
$n$ ~n~ dòng tiếp theo, dòng thứ $i$ ~i~ chứa $m-1$ ~m-1~ ký tự thuộc một trong $4$ ~4~ loại $P$ ~P~, $C$ ~C~, $Z$ ~Z~, $N$ ~N~, trong đó ký tự thứ $j$ ~j~ mô tả màu sắc của cánh cửa nối phòng $(i,j)$ ~(i,j)~ và phòng $(i,j+1)$ ~(i,j+1)~.
$n-1$ ~n-1~ dòng tiếp theo, dòng thứ $i$ ~i~ chứa $m$ ~m~ ký tự thuộc một trong $4$ ~4~ loại $P$ ~P~, $C$ ~C~, $Z$ ~Z~, $N$ ~N~, trong đó ký tự thứ $j$ ~j~ mô tả màu sắc của cánh cửa nối phòng $(i,j)$ ~(i,j)~ và phòng $(i+1,j)$ ~(i+1,j)~.
Dòng tiếp theo chứa số nguyên $q$ ~q~ $(1 \le q \le 100)$ ~(1 \le q \le 100)~.
$q$ ~q~ dòng tiếp theo, dòng thứ $i$ ~i~ chứa bốn số nguyên $a_i$ ~a_i~, $b_i$ ~b_i~, $c_i$ ~c_i~ và $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))$ mô tả câu hỏi của Alan.

Output

Với mỗi câu hỏi của Alan, in ra trên một dòng là số lượng màu cửa ít nhất phải băng qua để đi từ vị trí hiện tại ở phòng $(a_i,b_i)$ ~(a_i,b_i)~ đến lối thoát ở phòng $(c_i,d_i)$ ~(c_i,d_i)~.

Samples

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

Scoring

Subtask $1$ ~1~ với $17\%$ ~17\%~ số điểm: $n=1$ ~n=1~
Subtask $2$ ~2~ với $22\%$ ~22\%~ số điểm: Tất cả các cửa nối giữa hai phòng $(i,j)$ ~(i,j)~ và $(i,j+1)$ ~(i,j+1)~ đều có màu lam và tất cả các cửa nối giữa hai phòng $(i,j)$ ~(i,j)~ và $(i+1,j)$ ~(i+1,j)~ đều có màu đỏ
Subtask $3$ ~3~ với $29\%$ ~29\%~ số điểm: Tất cả các cửa đều có màu lam hoặc đỏ.
Subtask $4$ ~4~ với $32\%$ ~32\%~ số điểm: Không có ràng buộc gì thêm

Clarification

Hình sau mô tả mê cung trong ví dụ thứ $3$ ~3~.

Ở câu hỏi thứ tư, vị trí hiện tại của Alan và nhóm bạn đang ở phòng $(1,4)$ ~(1,4)~ (ký hiệu bởi chấm tròn trắng) và vị trí lối thoát ở phòng $(4,1)$ ~(4,1)~ (ký hiệu bởi chấm tròn đen). Đường đi băng qua ít màu cửa nhất với ba màu đỏ, lục và lam được minh họa như hình ảnh. Lưu ý rằng có thể tồn tại nhiều đường đi thỏa mãn, chỉ cần in ra số lượng màu cửa ít nhất.