Walking Home

Điểm: 1,00 (OI)

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

Python 3 5.0s

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

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Bessie muốn đi từ góc trái trên đến góc phải dưới của lưới $N \times N$ . Cô chỉ được đi sang phải (R) hoặc xuống dưới (D). Một số ô bị chặn bởi đống cỏ khô (ký hiệu H).

Bessie muốn đếm số đường đi hợp lệ sao cho số lần đổi hướng không quá $K$ (đổi hướng là khi bước tiếp theo khác hướng bước trước).

Cho $T$ bộ test, với mỗi bộ test hãy tìm số đường đi thỏa mãn.

Dữ liệu vào

Dòng $1$ : Số nguyên $T$ — số bộ test.
Với mỗi bộ test:
- Dòng đầu: Hai số nguyên $N$ và $K$ .
- $N$ dòng tiếp theo: Mỗi dòng gồm $N$ ký tự . (trống) hoặc H (bị chặn).

Dữ liệu ra

In $T$ dòng, mỗi dòng là số đường đi hợp lệ của bộ test tương ứng.

Ràng buộc

$1 \leq T \leq 50$ .
$2 \leq N \leq 50$ .
$1 \leq K \leq 3$ .
Ô $(1, 1)$ và $(N, N)$ luôn trống.

Ví dụ

Input	Output	Giải thích
7 3 1 ... ... ... 3 2 ... ... ... 3 3 ... ... ... 3 3 ... .H. ... 3 2 .HH HHH HH. 3 3 .H. H.. ... 4 3 ...H .H.. .... H...	2 4 6 2 0 0 6	Với $K = 1$ : chỉ có DDRR và RRDD. Với $K = 3$ không chướng ngại: cả $6$ hoán vị của $2$ D và $2$ R.

Bình luận

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