计算网格中的方块

Question

我有一个场景，其中我有一个带点的网格。例如，在下面的 m X n（即 5 X 6）网格的情况下，假设左上角是 0,0（第一行，第一列）。点 (1,1) , (1,3), (1,4),(2,3),(2,4),(3,1) 缺失。

我需要找出方格的数量。正方形的每一侧都应该填充点。所以下面的答案是 4（也包括外面的大方块）。所以我的问题是 A）什么是最好的方式来表示这个问题的输入和 B) 找到正方形的算法是什么。

正方形可以包含在另一个正方形中。所有方格都需要数。

......
. .  .
...  .
. ....
......

以下是我目前的逻辑。 i/p 是 1 和 0 的二维数组（1 是点，0 是间隙）。

set count=0
loop i =0 to m //each row
   loop j = 0 to n //each colum
         ifSquareFormedAt(i,j)
              count++
               

 func ifSquareFormedAt(i,j){
     ???? //what will be the logic here?
 }

Answer 1

具有 O(n^3) 复杂度的简单算法，其中 n 是矩形大小：

按行和按列计算累计和，因此 R[i][j] 包含 i-th 行中从左到 j-th 索引的个数，C[i][j] 包含个数j-th 列中的那些从顶部到 i-th 索引。

现在遍历所有可能的大小为 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 代码五结果 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

计算网格中的方块

Count the squares in the grid

java

algorithm

recursion

logic

count