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ụ.

enter image description here

  • 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
  • Có 15% số luợng test ứng với 15% số điểm có ~R, C \le 4; q \le 3~;
  • Có 15% số luợng test khác ứng với 15% số điểm có ~R = 1; q \le 3~;
  • Có 20% số luợng test khác ứng với 20% số điểm có ~R,C \le 100; q \le 3~;
  • Có 20% số luợng test khác ứng với 20% số điểm có ~R,C \le 1000; q \le 3~;
  • Có 10% số luợng test khác ứng với 10% số điểm có ~R,C \le 1000; q \le 10~;
  • Có 20% số luợng test còn lại ứng với 20% số điểm có ~R \times C \le 10^6; q \le 10~;
Example

Sample input

3 4 2
RDRD
RDRD
UUUL
1 1 3 2 
1 1 3 4

Sample 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~

Sample input

2 2 1
UD
RR
1 1 2 2

Sample 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


Be the first to comment

Comments

There are no comments at the moment.