英文:
Count the squares in the grid
问题
我有一个场景，在这个场景中有一个带有点的网格。例如，在下面这个 m 行 n 列（即 5 行 6 列）的网格中，假设左上角是 0,0（第一行，第一列）。缺少点 (1,1)、(1,3)、(1,4)、(2,3)、(2,4)、(3,1)。
我需要找出正方形的数量。每个正方形的每条边都应该有点填充。因此，在下面的例子中，答案是 4（其中也包括外部大正方形）。所以我的问题是：
A）表示此问题的输入的最佳方法是什么？
B）查找正方形的算法是什么？
正方形可以包含在另一个正方形中。所有的正方形都需要计数。
以下是我目前的逻辑。输入是一个由 1 和 0 组成的二维数组（1 表示点，0 表示空隙）。
设置 count=0
循环 i 从 0 到 m //每行
循环 j 从 0 到 n //每列
如果在(i,j)处形成正方形
count++
函数 ifSquareFormedAt(i,j){
逻辑是什么？
}
英文:
I have a scenario in which I have a grid with dots. For example in the below case of m X n (i.e. 5 X 6) grid, let's say top left is 0,0 (first row, first column). Dots (1,1) , (1,3), (1,4),(2,3),(2,4),(3,1) are missing.
I need to find the number of squares. Each side of the square should have dots filled. So below the answer would be 4 (which also includes the outer big square). So my question is
A) What is the best way to represent an input to this problem and
B) What is the algorithm to find the squares.
Squares can be enclosed within another. All squares need be counted.
......
. . .
... .
. ....
......
Below is the logic I have so far. The i/p is a 2D array of 1's and 0's (1's are the dots and 0's the gap).
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?
}
答案1
得分: 0
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)
Note: The code provided seems to have some errors, such as the usage of an undefined variable l and incorrect comparisons. It's advised to review and validate the code logic before using it.
英文:
Simple algorithm with O(n^3) complexity where n is rectangle size:
Calculate cumulative sums by rows and by columns, so R[i][j] contains number of ones in i-th row from the left upto j-th index, C[i][j] contains number of ones in j-th column from the top upto i-th index.
Now traverse through all possible squares of size k>1 having left top corner at [i][j]
Get row difference and compare it with k, do the same for column difference
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 code fives result 6 (outer rectangle is not square)
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
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论