Cho một bảng vuông \(n \times n\) , mỗi ô trên bảng có thể trống ('.') hoặc chứa chướng ngại vật ('X'). Hai ô gọi là kết nối trực tiếp với nhau nếu chung cạnh. Hai ô trống \((r_{1},\, c_{1})\) và \((r_{2},\, c_{2})\)  gọi là liên thông với nhau nếu tồn tại một chuỗi các ô trống bắt đầu \((r_{1},\, c_{1})\), kết thúc \((r_{2},\, c_{2})\), và hai ô trống liên tiếp bất kì trong dãy có kết nối trực tiếp đến nhau.

Dbom có thể phá hủy được tất cả các chướng ngai vật trong phạm vi hình vuông có kích thước \(k\, \times \, k\) bằng cách đặt bom, nhưng Dbom chỉ thực hiện việc phá hủy đó đúng một lần

Yêu cầu: hãy chọn hình vuông \(k \times k\) trên lưới để sau khi Dbom phá hủy sẽ thu được một vùng có nhiều ô trống liên thông nhất có thể. Tính số lượng ô trống của vùng liên thông này.

Dữ liệu vào:

+ Dòng đầu chứa 2 số \(n\) và \(k\) \((1\, \leq \, k\, \leq \, n\, \leq \, 100)\) lần lượt cho biết kích thước bảng và kích thước phạm vi Dbom có thể phá hủy trong một lần

+ Mỗi dòng trong \(n\) dòng sau chứa một xâu kí tự có độ dài \(n\). mô tả lại trạng thái của bảng ban đầu với ô trống sẽ được kí hiệu là '.' nếu có chướng ngại vật được kì hiệu là 'X'.

Kết quả:

+ In ra số lượng lớn nhất của vùng các ô trống liên thông với nhau sau khi được Dbom phá hủy các trường ngại vật trong phạm vi \(k \times \ k\).

Ví dụ:

Solution

Let's first find CC's (connected components) in the given grid, using DFS's.

We will consider every possible placement of a k × k square. When the placement is fixed then the answer is equal to the sum of k2 the the sum of sizes of CC's touching borders of the square (touching from outside), but for those CC's we should only count their cells that are outside of the square — not to count something twice. We will move a square, and at the same time for each CC we will keep the number of its cells outside the square.

We will used a sliding-window technique. Let's fix row of the grid — the upper row of the square. Then, we will first place the square on the left, and then we will slowly move a square to the right. As we move a square, we should iterate over cells that stop or start to belong to the square. For each such empty cell we should add or subtract 1 from the size of its CC (ids and sizes of CC's were found at the beginning).

And for each placement we consider, we should iterate over outside borders of the square (4k cells — left, up, right and down side) and sum up sizes of CC's touching our square. Be careful to not count some CC twice — you can e.g. keep an array of booleans and mark visited CC's. After checking all 4k cells you should clear an array, but you can't do it in O(number_of_all_components) because it would be too slow. You can e.g. also add visited CC's to some vector, and later in the boolean array clear only CC's from the vector (and then clear vector).

The complexity is O(n2·k).

Nguồn: http://codeforces.com/contest/680/problem/E