Painting Rectangle Version_I (public version)

Bài này có 2 version. Đây là version I.

Cho 1 lưới hình vuông kích thước n x n. Mỗi ô của lưới sẽ được tô màu đen (được biểu diễn bằng kí tự ‘#’) hoặc trắng (được biểu diễn bằng kí tự ‘.’). Bạn cần phải tô hình vuông sao cho mọi ô của lưới của được tô màu trắng. Với mỗi thao tác tô bạn sẽ chọn 1 hình chữ nhật có kích thước w * h (1 ≤ w,h ≤ n) và tô tất cả ô trong hình chữ nhật này thành màu trắng. Chi phí cho mỗi lần tô là max(w,h). Bạn hãy tìm chi phí tô nhỏ nhất sao cho có thể tô tất cả ô thành màu trắng.

Ví dụ:

• Với n = 5 và lưới hình vuông 5 x 5 như dưới đây:

• #...#
  .#.#.
  .....
  .#...
  #....

• Chi phí nhỏ nhất là 5, bằng việc tô hình chữ nhật có kích thước 5 x 5 với chi phí bằng max(5,5) = 5.

[Đầu vào/Đầu ra]:

• [Giới hạn thời gian]: 2s với C++, 12s với Java & C#, 16s với Python,Go,Js.
• [Đầu vào]: Số tự nhiên n (1 ≤ n ≤ 50) biểu thị kích thước của lưới hình vuông n x n.
• [Đầu vào]: n vector chứa các xâu độ dài n tương đương với hàng thứ i. Kí tự ‘#’ đại diện cho ô được tô màu đen, kí tự ‘.’ đại diện cho ô tô màu trắng.
• [Đầu ra]: Chi phí nhỏ nhất để tô tất cả ô thành màu trắng.

[Mô tả các test]:

• Test 1 → 40: 1 ≤ n ≤ 50.
• Test 41 → 101: n = 50.