简单算法 O(n^3) 复杂性在哪里 n 是矩形大小：
按行和列计算累计和，所以 R[i][j] 包含从左侧到第j个索引的第i行中的个数， C[i][j] 包含从顶部到第i个索引的第j列中的个数。
现在遍历所有可能的大小方格 k>1 左上角 [i][j] 获取行差并将其与k进行比较，对列差执行相同的操作

for all nonzero i,j:
  for k=1..min(width-j, height-i):
    if nonzero(i+k, j+k):
        if R[i][j+k] - R[i][j] != k   //top row difference
           break                     //there are holes in this row between i and i+k
        if C[i+k][j] - C[i][j] != k   //left column difference
           break  
        if R[i+k][j+k] - R[i+k][j] != k   //bottom row difference
           break                     //there are holes in this row between i and i+k
        if C[i+k][j+k] - C[i][j+l] != k   //right column difference
           break  

        count +=1   //we reached this point, so all sides are good

python代码5结果6（外部矩形不是正方形）

def nonzero(a, y, x):
    return 1 if a[y][x]=='.' else 0

w = 6
h = 5
a = ['......', '. .  .', '...  .', '. ....', '......']
r = [[0]*w for i in range(h)]
c = [[0]*w for i in range(h)]
for i in range(h):
    for j in range(w):
        val = nonzero(a, i, j)
        if i==0:
            c[i][j] = val
        else:
            c[i][j] = c[i-1][j]  + val
        if j==0:
            r[i][j] = val
        else:
            r[i][j] = r[i][j-1] + val
count = 0
for i in range(h - 1):
    for j in range(w - 1):
        if nonzero(a, i, j):
            for k in range(1, min(h-i, w-j)):
                if nonzero(a, i+k, j+k):
                    if r[i][j+k] - r[i][j] != k :
                        break      #there are holes in this row between i and i+k
                    if c[i+k][j] - c[i][j] != k:
                        break
                    if r[i+k][j+k] - r[i+k][j] != k:
                        break
                    if c[i+k][j+k] - c[i][j+k] != k:
                        break
                    count += 1
                    print(i, j, k)
print(count)

0 0 2
0 2 3
2 0 2
3 2 1
3 3 1
3 4 1
6