Educational Backtracking: Điền chữ L

Xem dạng PDF

Gửi bài giải


Điểm: 0,30 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Cho bảng hình chữ nhật gồm ~N~ hàng, ~M~ cột. Các ô trong bảng thuộc một trong hai trạng thái: rỗng hoặc không rỗng. Các ô rỗng chứa ký tự '.', các ô không rỗng chứa ký tự '#'.

Bạn được phép xếp các hình thuộc một trong hai dạng sau đây vào bảng:

image

Bạn cần kiểm tra xem có tồn tại một cách xếp sao cho mỗi ô rỗng thuộc đúng một hình và các ô không rỗng không thuộc hình nào. Lưu ý: Bạn không được xoay hay lật các hình được cho.

Input

Dòng đầu tiên gồm hai số nguyên dương ~N, M~ ~(2 \leq N, 2 \leq M, N*M \leq 16)~. ~N~ dòng tiếp theo, mỗi dòng gồm ~M~ ký tự thể hiện một hàng của bảng.

Output

In ra một dòng duy nhất gồm xâu ký tự "YES" nếu thực hiện được yêu cầu của đề bài, nếu không in ra "NO".

Sample Input 1

4 4
##.#
#..#
.#.#
....

Sample Output 1

YES

Sample Input 2

4 4
#..#
....
....
#..#

Sample Output 2

NO

Sample Input 3

4 4
#..#
...#
....
#..#

Sample Output 3

NO

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.