{"code":"thttinhbc5","name":"Robot (THT BC Vòng Tỉnh/TP 2022)","description":"###Robot (Bài 3 bảng C2, Bài 2 bảng C1)\r\n\r\nMinh 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. \r\n\r\nVí dụ, bảng phía dưới là một ví dụ.\r\n\r\n![enter image description here][1]\r\n\r\n-\tRobot ban\tđầu ở vị trí ô ($1,1$), buớc tiếp theo robot\tsẽ di\tchuyển sang phải tới ô ($1, 2$).\r\n-\tỞ ô\t($1, 2$),\trobot nhận chỉ\tdẫn di\tchuyển tiếp xuống\tduới\tlà ô ($2, 2$).\r\n-\tỞ ô\t($2, 2$),\trobot nhận chỉ\tdẫn di\tchuyển tiếp xuống\tduới\tlà ô ($3, 2$).\r\n-\tỞ ô\t($3, 2$),\trobot nhận chỉ\tdẫn di\tchuyển lên trên là ô ($2,\t2$).\r\n-\tRobot sẽ di chuyển giữa hai ô ($2, 2$) và ($3, 2$).\r\n\r\nMinh 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:\r\n-\tTồ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.\r\n-\tTồ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.\r\n\r\n\r\n####Input \r\n-\tDò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;\r\n-\tTiế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;\r\n•\t$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.\r\n\r\n####Output\r\n- 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$).\r\n\r\n####Scoring\r\n- Subtask $1$ ($15\\%$ số điểm): $R, C \\le 4; q \\le 3$; \r\n- Subtask $2$ ($15\\%$ số điểm): $R = 1; q \\le 3$;\r\n- Subtask $3$ ($20\\%$ số điểm): $R,C \\le 100; q \\le 3$;\r\n- Subtask $4$ ($20\\%$ số điểm): $R,C \\le 1000; q \\le 3$;\r\n- Subtask $5$ ($10\\%$ số điểm): $R,C \\le 1000; q \\le 10$;\r\n- Subtask $6$ ($20\\%$ số điểm): $R \\times C \\le 10^6; q \\le 10$;\r\n\r\n\r\n####Example\r\n!!! question \"Test 1\"\r\n    ???+ \"Input\"\r\n        ```sample\r\n        3 4 2\r\n        RDRD\r\n        RDRD\r\n        UUUL\r\n        1 1 3 2 \r\n        1 1 3 4 \r\n        ```\r\n    ???+ success \"Output\"\r\n        ```sample\r\n        0 1\r\n        1 3\r\n        ```\r\n    ??? warning \"Note\"\r\n        - *Trường hợp đầu tiên không cần thay đổi chỉ dẫn dẫn nào*\r\n        - *Trường hợp thứ hai, chỉ cần thay đổi 1 ô  bằng 1 trong 3 cách sau:*\r\n            - ô ($1,2$) từ $D$ sang $R$\r\n            - ô ($2,2$) từ $D$ sang $R$\r\n            -  ô ($3,2$) từ $U$ sang $R$\r\n!!! question \"Test 2\"\r\n    ???+ \"Input\"\r\n        ```sample\r\n        2 2 1\r\n        UD\r\n        RR\r\n        1 1 2 2 \r\n        ```\r\n    ???+ success \"Output\"\r\n        ```sample\r\n        1 2\r\n        ```\r\n    ??? warning \"Note\"\r\n        *Thay đổi chỉ dẫn ô ($1,1$) từ U thành R hoặc D đều có thể đưa robot đến đích*\r\n\r\n\r\n        [1]: https://i.imgur.com/51OG11e.png","points":200.0,"partial":false,"time_limit":1.0,"memory_limit":262144,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}