Duyên hải Bắc Bộ 2024 - 10 - Mê cung ngoặc

Xem dạng PDF

Gửi bài giải

Điểm: 70,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 1G
Input: stdin
Output: stdout

Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Pascal, PyPy, Python, Scratch, TEXT

Trong 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

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.