Mê cung ngoặc

Điểm: 4,00 (OI)

Giới hạn thời gian: 2.0s

Giới hạn bộ nhớ: 256M

Input: stdin

Output: stdout

Nguồn bài:

23-24 DHBB K10 K11

Dạng bài

Ngôn ngữ cho phép

C, C#, C++, Java, Javascript, Kotlin, Pascal, Python, Scratch

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 được mô tả trong hình trên, cụ thể: từ ô đang đứng, căn cứ vào hướng đang hướng tới được chỉ ra bởi mũi tên $\to$ , 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 (các hướng có thể di chuyển được chỉ ra bởi các mũi tên $\to$ ). 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ì $A B$ 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$ .

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.

Dữ liệu vào

Dòng đầu tiên ghi ba số nguyên dương $m, n, k$ ( $m, n \leq 30$ ; $k \leq 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 ).

Dữ liệu ra

Một dòng là số lượng đường đi đếm được chia dư cho ( $10^{9} + 7$ ).

Ràng buộc

$m, n \leq 30$ ; $k \leq 10$
Subtask 1 (50 điểm): $m, n \leq 5$
Subtask 2 (25 điểm): $k = 1$
Subtask 3 (25 điểm): Không có ràng buộc gì thêm.

Ví dụ

Input	Output	Giải thích
3 3 1 ()) )() )))	4

Bình luận

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