Duyên hải Bắc Bộ 2024 - 10 - Mê cung ngoặc
Xem dạng PDFTrong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài
Một mê cung được mô tả bằng bảng chữ hình chữ nhật kích thước ~m \times n~. Các hàng của bảng được đánh số từ ~1~ đến ~m~, từ trên xuống dưới, các cột của bảng được đánh số từ ~1~ đến ~n~, từ trái qua phải. Ô nằm trên giao của hàng ~i~ và cột ~j~ được gọi là ô ~(i, j)~. Mỗi ô của lưới chứa một kí tự ngoặc mở '(' hoặc ngoặc đóng ')'.
Người chơi sẽ xuất phát từ ô ~(1, 1)~, quay hướng tới phía ô ~(1, n)~ và di chuyển trên bảng. Việc di chuyển phải tuân thủ các quy tắc sau: từ ô đang đứng, căn cứ vào hướng đang hướng tới, thực hiện bước di chuyển sang ô kề cạnh đang hướng tới, hoặc sang ô kề cạnh nằm bên phải. Mỗi ô chỉ được đi qua nhiều nhất một lần. Người chơi có thể dừng di chuyển tại một ô nào đó để kết thúc trò chơi.
Khi kết thúc trò chơi, người chơi nhận được một xâu kí tự ~T~ gồm các kí tự trong các ô trên đường đi được xếp liên tiếp nhau. Người chơi giành chiến thắng nếu xâu ~T~ là một biểu thức ngoặc đúng bậc ~k~.
Nhắc lại, định nghĩa biểu thức ngoặc đúng và bậc của biểu thức ngoặc.
Biểu thức rỗng là biểu thức ngoặc đúng và có bậc bằng ~0~,
Nếu ~A~ là biểu thức ngoặc đúng có bậc bằng ~k~ thì ~(A)~ cũng là một biểu thức ngoặc đúng có bậc bằng ~k+1~,
Nếu ~A~ và ~B~ là hai biểu thức ngoặc đúng và có bậc tương ứng là ~k_1~ và ~k_2~ thì ~AB~ cũng là một biểu thức ngoặc đúng có bậc bằng ~\max(k_1, k_2)~.
Ví dụ, '()(())' là một biểu thức ngoặc đúng có bậc bằng ~2~ còn '(()(()))' là một biểu thức ngoặc đúng và có bậc bằng ~3~.
Yêu cầu: Cho bảng chữ và số nguyên dương ~k~, đếm số lượng đường đi khác nhau giúp người chơi giành chiến thắng. Hai đường đi được gọi là khác nhau nếu tồn tại một ô thuộc đường đi này nhưng không thuộc đường đi kia.
Input
Dòng đầu tiên ghi ba số nguyên dương ~m, n, k~ (~m, n \le 30~; ~k \le 10~);
Tiếp theo là ~m~ dòng mô tả bảng chữ, mỗi dòng chứa một xâu gồm ~n~ kí tự, mỗi kí tự ngoặc mở '(' hoặc ngoặc đóng ')'.
Output
Một dòng là số lượng đường đi đếm được chia dư cho ~(10^9 + 7)~.
Scoring
| Subtask | Điểm | Ràng buộc |
|---|---|---|
| 1 | ~50\%~ | ~m, n \le 5~ |
| 2 | ~25\%~ | ~k = 1~ |
| 3 | ~25\%~ | Không có ràng buộc gì thêm. |
Sample Input 1
3 3 1
())
)()
)))
Sample Output 1
4
Bình luận