Hình vuông đen

Đề bài

Mô tả

Cho một tờ giấy kẻ ô kích thước n×m. 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 n và m: số hàng và số cột của tờ giấy.
  • n dòng tiếp theo, mỗi dòng chứa m 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 −1.

Ràng buộc

  • 1≤n,m≤100

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 3×3−4=5 ô.
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

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

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0