Robot (Bài 3 bảng C2, Bài 2 bảng C1)
Minh mới tạo ra một robot có khả năng nhận dạng trên sàn và di chuyển theo các chỉ dẫn đó. Sàn là một bảng gồm R hàng và C cột. Các hàng được đánh số từ 1 đến R từ trên xuống duới, các cột đuợc đánh số từ 1 đến C từ trái sang phải. Ô ở hàng thứ u\ (1 \le u \le R) và cột thứ v\ (1 \le v \le C) đuợc gọi là ô (u,v). Mồi ô của bảng sẽ có chỉ dẫn cho buớc đi tiếp theo cho robot.
Ví dụ, bảng phía dưới là một ví dụ.
- Robot ban đầu ở vị trí ô (1,1), buớc tiếp theo robot sẽ di chuyển sang phải tới ô (1, 2).
- Ở ô (1, 2), robot nhận chỉ dẫn di chuyển tiếp xuống duới là ô (2, 2).
- Ở ô (2, 2), robot nhận chỉ dẫn di chuyển tiếp xuống duới là ô (3, 2).
- Ở ô (3, 2), robot nhận chỉ dẫn di chuyển lên trên là ô (2, 2).
- Robot sẽ di chuyển giữa hai ô (2, 2) và (3, 2).
Minh muốn thử nghiệm đua robot di chuyển từ ô (x_s, y_s) tới đuợc ô (x_t, y_t) nhung bảng huớng dẫn có thể không làm cho robot di chuyển đuợc nhu vậy. Bạn đuợc quyền thay đồi huớng dẫn của một số ô để robot có thể đi từ (x_s,y_s) đến (x_t,y_t). Nhiệm vụ của bạn là chọn ít nhất các ô và thay đổi chỉ dẫn của các ô này để robot có thể đi từ đi từ (x_s,y_s) đến (x_t,y_t). Nếu có nhiều cách thay đổi chỉ dẫn các ô, hãy đếm số cách thay đổi khác nhau. Truờng hợp không cần thay đổi ô nào thì số cách là 1. Nguợc lại, hai cách thay đổi đuợc coi là khác nhau nếu một trong hai điều sau xảy ra:
- Tồn tại một ô được thay đồi trong cách thứ nhất mà không đuợc thay đổi trong cách thứ hai.
- Tồn tại một ô được thay đổi trong cả hai cách, nhưng chỉ dẫn sau khi thay đồi ở cách thứ nhất khác cách thứ hai.
Input
- Dòng đầu chứa ba số R, C và q, trong đó R, C là kích thuớc của bảng và q là số truờng hợp thứ nghiệm;
- Tiếp theo là R dòng, mỗi dòng chửa xâu kí tụ độ dài C. Kí tụ thứ v trên dòng thứ u, thể hiện chỉ dẫn của ô (u, v). Chỉ dẫn thuộc một trong 4 kí tự U, D, L, R tương ứng với đi lên trên, xuống duới, sang trái, sang phải;
• q dòng cuối, mỗi dòng chứa bốn số nguyên x_s, y_s, x_t, y_t tương ứng với một thử nghiệm.
Output
- Ghi ra gồm q dòng, mỗi dòng gồm hai số cách nhau một dấu cách: số thứ nhất ghi ra số ô phải thay đổi ít nhất, số thứ hai là phần dư trong phép chia số cách thay đổi khác nhau chia cho (10^9 + 7).
Scoring
- Subtask 1 (15\% số điểm): R, C \le 4; q \le 3;
- Subtask 2 (15\% số điểm): R = 1; q \le 3;
- Subtask 3 (20\% số điểm): R,C \le 100; q \le 3;
- Subtask 4 (20\% số điểm): R,C \le 1000; q \le 3;
- Subtask 5 (10\% số điểm): R,C \le 1000; q \le 10;
- Subtask 6 (20\% số điểm): R \times C \le 10^6; q \le 10;
Example
Test 1
Input
3 4 2
RDRD
RDRD
UUUL
1 1 3 2
1 1 3 4
Output
0 1
1 3
Note
- Trường hợp đầu tiên không cần thay đổi chỉ dẫn dẫn nào
- Trường hợp thứ hai, chỉ cần thay đổi 1 ô bằng 1 trong 3 cách sau:
- ô (1,2) từ D sang R
- ô (2,2) từ D sang R
- ô (3,2) từ U sang R
Test 2
Input
2 2 1
UD
RR
1 1 2 2
Output
1 2
Note
Thay đổi chỉ dẫn ô (1,1) từ U thành R hoặc D đều có thể đưa robot đến đích
Comments