Robot (THT BC Vòng Tỉnh/TP 2022)

View as PDF

Submit solution

Points: 200
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Author:
Problem type

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, Cq, 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

There are no comments at the moment.