Hình vuông đen
Đề bài
Mô tả
Cho một tờ giấy kẻ ô kích thước . Mỗi ô đã được tô màu đen hoặc để trắng.
Bạn muốn tô thêm màu đen cho một số ô trắng sao cho sau khi tô xong, tập hợp tất cả các ô đen tạo thành đúng một hình vuông đặc có các cạnh song song với cạnh tờ giấy. Nghĩa là mọi ô nằm trong hình vuông đó đều phải đen, và mọi ô nằm ngoài hình vuông đó đều phải trắng. Cạnh hình vuông phải có độ dài nguyên dương.
Lưu ý bạn chỉ được tô trắng thành đen, không được xoá một ô đen đã có. Do đó mọi ô đen ban đầu bắt buộc phải nằm trong hình vuông kết quả.
Hãy tìm số ô ít nhất cần tô thêm, hoặc cho biết điều đó là không thể.
Dữ liệu vào
- Dòng đầu chứa hai số nguyên và : số hàng và số cột của tờ giấy.
- dòng tiếp theo, mỗi dòng chứa ký tự 'B' hoặc 'W' mô tả màu ban đầu của các ô. Ký tự 'B' là ô đen, 'W' là ô trắng.
Dữ liệu ra
In ra số ô ít nhất cần tô thêm màu đen để các ô đen tạo thành một hình vuông đặc. Nếu không thể, in ra .
Ràng buộc
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 5 4 WWWW WWWB WWWB WWBB WWWW |
5 | Bốn ô đen ban đầu nằm gọn trong khung từ hàng 2 đến hàng 4 và từ cột 3 đến cột 4, tức cao 3 và rộng 2. Hình vuông nhỏ nhất chứa được khung này có cạnh 3. Đặt hình vuông cạnh 3 với góc trên trái tại hàng 2, cột 2 thì cần tô thêm ô. |
| 1 2 BB |
-1 | Hai ô đen nằm trên cùng một hàng và cách nhau 2 cột, nên hình vuông phải có cạnh ít nhất 2. Nhưng tờ giấy chỉ cao 1 hàng, không chứa nổi hình vuông cạnh 2. |
| 3 3 WWW WWW WWW |
1 | Chưa có ô đen nào. Tô bất kỳ một ô cũng tạo thành hình vuông cạnh 1, nên đáp án là 1 chứ không phải 0. |
Bình luận