Hình dấu cộng
Đề bài
Mô tả
Cho một bức tranh kích thước gồm các ô trống (ký hiệu .) và các ô được tô (ký hiệu *).
Hãy xác định xem bức tranh có đúng một hình dấu cộng + hay không. Một hình dấu cộng được mô tả như sau:
- Có đúng một ô tâm được tô.
- Từ ô tâm, theo mỗi hướng trong bốn hướng (trái, phải, lên, xuống) có ít nhất một ô được tô liên tiếp. Nói cách khác, mỗi hướng đều phải có một tia với độ dài ít nhất .
- Tất cả các ô còn lại của bức tranh đều trống.
Bốn tia không nhất thiết phải có cùng độ dài. Tuy nhiên, chỉ cần tồn tại thêm một ô được tô nằm ngoài hình dấu cộng, hoặc hình vẽ có bề dày lớn hơn một ô ở đâu đó, thì câu trả lời là không.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên và : chiều cao và chiều rộng của bức tranh.
- dòng tiếp theo, dòng thứ chứa xâu độ dài gồm các ký tự
.và*, trong đó.là ô trống và*là ô được tô.
Dữ liệu ra
In ra YES nếu bức tranh là đúng một hình dấu cộng, ngược lại in ra NO.
Ràng buộc
- chỉ gồm các ký tự
.và*
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 5 6 ...... ..*... .****. ..*... ..*... |
YES | Tâm nằm ở hàng , cột . Bốn tia có độ dài lần lượt là (lên), (xuống), (trái), (phải). Bốn tia không cùng độ dài nhưng điều đó vẫn hợp lệ. |
| 3 5 .... **. .... |
NO | Hai nhánh dọc nằm ở hai cột khác nhau nên không có ô nào đóng vai trò tâm. |
| 5 6 ..**.. .... **** ..**.. ..**.. |
NO | Hai nhánh dọc có bề rộng bằng , hình vẽ không phải dấu cộng có bề dày một ô. |
| 7 7 ....... ...*... ..****. ...*... ...*... ....... .*..... |
NO | Có một ô được tô nằm ngoài hình dấu cộng (hàng , cột ). |
| 3 7 ..... . ..... |
NO | Bức tranh chứa hai hình dấu cộng chứ không phải một. |
| 5 10 .......... ..*....... ..*****. ..*....... .......... |
NO | Có một ô trống nằm bên trong hình vẽ, tia phải bị ngắt quãng. |
Bình luận