Notice that if somewhere in the table there is a diamond shape whose edge is made out of #, then its interior is also a diamond shape, but its edge is from . instead of #. Therefore, it is enough to iterate over the table and using BFS or DFS, find the maximal connected regions made from . and for each such region, check if it has a diamond shape.

Let's now look at all cells ~(i, j)~ for which ~i+j = k~, for some fixed value of ~k~. It's easy to see that those cells will form a diagonal in the table going in the direction from bottom-left to top-right. Also, smaller values of ~k~ correspond to diagonals closer to the top-left corner of the table, while larger values of ~k~ correspond to diagonals closer to the bottom-right corner of the table. In a similar way, the set of cells for which ~i-j = k~ forms a diagonal, but in the other direction. This means that if we are given fixed numbers ~a~, ~b~, ~c~ and ~d~ such that ~a \le b~ and ~c \le d~, then the set of all cells ~(i, j)~ for which ~a \le i+j \le b~ and ~c \le i-j \le d~ actually forms a tilted rectangle. In case ~b-a = d-c~, it is actually a tilted square, i.e. a diamond.

Therefore, to check if some region is a diamond or not, we keep track of the following: the number of visited cells (cnt), and the minimum and maximum diagonal in both directions (~a = \min(i+j)~, ~b = \max(i+j)~, ~c = \min(i-j)~, ~d = \max(i-j)~). What remains is to check whether ~b-a = d-c~ and to see if the number of visited cells matches the number of cells that should be in the diamond of this size (~b-a~). In doing so, we need to calculate the number of . in a diamond of size ~n~, which turns out to be ~n^2+(n-1)^2~.