我隨機生成了包含 0 和 1 的網格：1 1 0 0 0 1 0 11 1 1 0 1 1 1 11 0 0 0 1 0 1 10 0 1 0 1 0 1 11 1 1 1 0 0 1 10 0 1 1 1 1 1 00 1 0 0 1 0 1 1如何迭代網格以找到最大的 1s 簇，即等于或大于 4 個項目（跨行和列）？我假設我需要在迭代時對每個找到的簇進行計數，并且其超過 4 個項目，在列表中記錄和計數，然后找到最大的數字。問題是我無法弄清楚如何跨行和列執行此操作并記錄計數。我已經迭代了網格，但不確定如何移動超過兩行。例如在上面的例子中，最大的簇是8。網格中還有一些其他簇，但它們有4個元素：AA 0 0 0 1 0 1A A 1 0 1 1 1 1 10 0 0 1 0 1 1 0 0 1 0 1 0 1 1 1 1 BB 0 0 1 1 0 0 BB 1 1 1 0 0 1 0 0 1 0 1 1我嘗試過的代碼：rectcount = []for row in range(len(grid)): for num in range(len(grid[row])): # count = 0 try: # if grid[row][num] == 1: # if grid[row][num] == grid[row][num + 1] == grid[row + 1][num] == grid[row + 1][num + 1]: # count += 1 if grid[row][num] == grid[row][num + 1]: if grid[row + 1][num] == grid[row][num + 1]: count += 1 # if grid[row][num] == grid[row][num + 1] and grid[row][num] == grid[row + 1][num]: # count += 1 else: count = 0 if grid[row][num] == grid[row + 1][num]: count += 1 except: pass
1 回答
回首憶惘然
TA貢獻1847條經驗 獲得超11個贊
我已經實現了三種算法。
第一個算法是Simple，使用最簡單的嵌套循環方法，它具有O(N^5) 時間復雜度（對于我們的情況N，其中 是輸入網格的一側10），對于我們的輸入大小10x10時間來說O(10^5)是相當好的。代碼中的算法 ID 是algo = 0。如果您只想查看該算法，請跳轉到------ Simple Algorithm代碼內的行。
第二種算法是Advanced，采用動態規劃方法，其復雜度O(N^3)比第一種算法快得多。代碼中的算法 ID 是algo = 1。跳轉到------- Advanced Algorithm代碼內的行。
我實現的第三個算法Simple-ListComp只是為了好玩，它幾乎與 相同Simple，相同的O(N^5)復雜性，但使用 Python 的列表理解而不是常規循環，這就是為什么它更短，也慢一點，因為沒有使用一些優化。代碼中的算法 ID 是algo = 2。跳轉到------- Simple-ListComp Algorithm代碼內的行以查看算法。
除了算法之外，其余代碼還實現檢查結果的正確性（算法之間的雙重檢查）、打印結果、生成文本輸入。代碼分為解決任務函數solve()和測試函數test()。solve()函數有許多參數來允許配置函數的行為。
所有主要代碼行均由注釋記錄，閱讀它們以了解如何使用代碼。基本上，如果s變量包含帶有網格元素的多行文本，就像您的問題一樣，您只需運行solve(s, text = True)它就會解決任務并打印結果。algo = 0, check = False此外，您還可以通過給出求解函數的下一個參數（此處 0 表示算法 0 ）從兩個版本（0（簡單）和 1（高級）和 2（簡單列表計算））中選擇算法。查看test()函數體以查看最簡單的用法示例。
算法默認輸出到控制臺的所有簇，從最大到最小，最大的用.符號表示，其余的用B, C, D, ...,Z符號表示。show_non_max = False如果您只想顯示第一個（最大）簇，您可以在求解函數中設置參數。
我將解釋簡單算法：
基本上算法的作用是 - 它搜索所有可能的有角度的
1s矩形并將其中最大的矩形的信息存儲到ma二維數組中。Top-left這個矩形的點是(i, j),top-right-(i, k),bottom-left-(l, j + angle_offset),bottom-right-(l, k + angle_offset)，所有 4 個角，這就是我們有這么多循環的原因。在外部兩個
i（行）、j（列）循環中，我們迭代整個網格，該(i, j)位置將是矩形top-left的點1s，我們需要迭代整個網格，因為所有可能的1s矩形可能位于整個網格的top-left任何點。(row, col)在循環開始時，j我們檢查位置處的網格應(i, j)始終包含1，因為在循環內部我們僅搜索所有矩形1s。k循環遍歷矩形的所有可能top-right位置。如果等于，我們應該跳出循環，因為沒有必要進一步向右擴展，因為這樣的矩形將始終包含。(i, k)1s(i, k)0k0在之前的循環中，我們固定了
top-left矩形top-right的角點。現在我們需要搜索兩個底角。為此，我們需要以不同角度向下延伸矩形，直到到達第一個0。off循環嘗試以所有可能的角度向下延伸矩形（0（垂直垂直），+1（45從上到下向右移動的度數），-1（-45度）），off基本上是grid[y][x]“上方”的數字（對應于 byY）grid[y + 1][x + off]。lY嘗試以不同角度向下（方向）延伸矩形off。它被擴展到第一個，0因為它不能進一步擴展（因為每個這樣的矩形已經包含0）。循環內部
l有一個if grid[l][max(0, j + off * (l - i)) : min(k + 1 + off * (l - i), c)] != ones[:k - j + 1]:條件，基本上這if是為了檢查矩形的最后一行是否包含所有內容，1如果不是，if則會跳出循環。此條件比較兩個list切片是否相等。矩形的最后一行從點(l, j + angle_offset)（表達式max(0, j + off * (l - i))，最大限制為0 <= X）到點(l, k + angle_offset)（表達式min(k + 1 + off * (l - i), c)，最小限制為X < c）。在循環內部
l還有其他行，ry, rx = l, k + off * (l - i)計算bottom-right矩形的點，(ry, rx)即(l, k + angle_offset)，該(ry, rx)位置用于存儲在ma數組中找到的最大值，該數組存儲所有找到的最大矩形，包含有關在點ma[ry][rx]處的矩形的信息。bottom-right(ry, rx)rv = (l + 1 - i, k + 1 - j, off)line 計算ma[ry][rx]數組條目的新的可能候選者，之所以可能，ma[ry][rx]是因為僅當新候選者具有更大的面積時才更新1s。這里元組rv[0]內的值rv包含height這樣的矩形，rv[1]包含width這樣的矩形（width等于矩形底行的長度），rv[2]包含這樣的矩形的角度。條件
if rv[0] * rv[1] > ma[ry][rx][0] * ma[ry][rx][1]:及其主體僅檢查rv面積是否大于數組內的當前最大值ma[ry][rx]，如果大于則更新此數組條目（ma[ry][rx] = rv）。我會提醒您，其中包含有關當前找到的最大面積矩形的ma[ry][rx]信息，該矩形具有、和。(width, height, angle)bottom-right(ry, rx)widthheightangle完畢！算法運行后，數組
ma包含有關所有最大面積有角度的矩形（簇）的信息1s，以便所有簇都可以恢復并稍后打印到控制臺。Largest of all such1s-clusters 等于 somerv0 = ma[ry0][rx0]，只需迭代一次 的所有元素ma并找到這樣的點(ry0, rx0)，以使ma[ry0][rx0][0] * ma[ry0][rx0][1]（面積）最大。然后最大的簇將有bottom-rightpoint(ry0, rx0)、bottom-leftpoint(ry0, rx0 - rv0[1] + 1)、top-rightpoint(ry0 - rv0[0] + 1, rx0 - rv0[2] * (rv0[0] - 1))、top-leftpoint(ry0 - rv0[0] + 1, rx0 - rv0[1] + 1 - rv0[2] * (rv0[0] - 1))（這里只是角度偏移，即第一行與矩形的最后一行相比rv0[2] * (rv0[0] - 1)移動了多少）。X
# ----------------- Main function solving task -----------------
def solve(
grid, *,
algo = 1, # Choose algorithm, 0 - Simple, 1 - Advanced, 2 - Simple-ListComp
check = True, # If True run all algorithms and check that they produce same results, otherwise run just chosen algorithm without checking
text = False, # If true then grid is a multi-line text (string) having grid elements separated by spaces
print_ = True, # Print results to console
show_non_max = True, # When printing if to show all clusters, not just largest, as B, C, D, E... (chars from "cchars")
cchars = ['.'] + [chr(ii) for ii in range(ord('B'), ord('Z') + 1)], # Clusters-chars, these chars are used to show clusters from largest to smallest
one = None, # Value of "one" inside grid array, e.g. if you have grid with chars then one may be equal to "1" string. Defaults to 1 (for non-text) or "1" (for text).
offs = [0, +1, -1], # All offsets (angles) that need to be checked, "off" is such that grid[i + 1][j + off] corresponds to next row of grid[i][j]
debug = False, # If True, extra debug info is printed
):
# Preparing
assert algo in [0, 1, 2], algo
if text:
grid = [l.strip().split() for l in grid.splitlines() if l.strip()]
if one is None:
one = 1 if not text else '1'
r, c = len(grid), len(grid[0])
sgrid = '\n'.join([''.join([str(grid[ii][jj]) for jj in range(c)]) for ii in range(r)])
mas, ones = [], [one] * max(c, r)
# ----------------- Simple Algorithm, O(N^5) Complexity -----------------
if algo == 0 or check:
ma = [[(0, 0, 0) for jj in range(c)] for ii in range(r)] # Array containing maximal answers, Lower-Right corners
for i in range(r):
for j in range(c):
if grid[i][j] != one:
continue
for k in range(j + 1, c): # Ensure at least 2 ones along X
if grid[i][k] != one:
break
for off in offs:
for l in range(i + 1, r): # Ensure at least 2 ones along Y
if grid[l][max(0, j + off * (l - i)) : min(k + 1 + off * (l - i), c)] != ones[:k - j + 1]:
l -= 1
break
ry, rx = l, k + off * (l - i)
rv = (l + 1 - i, k + 1 - j, off)
if rv[0] * rv[1] > ma[ry][rx][0] * ma[ry][rx][1]:
ma[ry][rx] = rv
mas.append(ma)
ma = None
# ----------------- Advanced Algorithm using Dynamic Programming, O(N^3) Complexity -----------------
if algo == 1 or check:
ma = [[(0, 0, 0) for jj in range(c)] for ii in range(r)] # Array containing maximal answers, Lower-Right corners
for off in offs:
d = [[(0, 0, 0) for jj in range(c)] for ii in range(c)]
for i in range(r):
f, d_ = 0, [[(0, 0, 0) for jj in range(c)] for ii in range(c)]
for j in range(c):
if grid[i][j] != one:
f = j + 1
continue
if f >= j:
# Check that we have at least 2 ones along X
continue
df = [(0, 0, 0) for ii in range(c)]
for k in range(j, -1, -1):
t0 = d[j - off][max(0, k - off)] if 0 <= j - off < c and k - off < c else (0, 0, 0)
if k >= f:
t1 = (t0[0] + 1, t0[1], off) if t0 != (0, 0, 0) else (0, 0, 0)
t2 = (1, j - k + 1, off)
t0 = t1 if t1[0] * t1[1] >= t2[0] * t2[1] else t2
# Ensure that we have at least 2 ones along Y
t3 = t1 if t1[0] > 1 else (0, 0, 0)
if k < j and t3[0] * t3[1] < df[k + 1][0] * df[k + 1][1]:
t3 = df[k + 1]
df[k] = t3
else:
t0 = d_[j][k + 1]
if k < j and t0[0] * t0[1] < d_[j][k + 1][0] * d_[j][k + 1][1]:
t0 = d_[j][k + 1]
d_[j][k] = t0
if ma[i][j][0] * ma[i][j][1] < df[f][0] * df[f][1]:
ma[i][j] = df[f]
d = d_
mas.append(ma)
ma = None
# ----------------- Simple-ListComp Algorithm using List Comprehension, O(N^5) Complexity -----------------
if algo == 2 or check:
ma = [
[
max([(0, 0, 0)] + [
(h, w, off)
for h in range(2, i + 2)
for w in range(2, j + 2)
for off in offs
if all(
cr[
max(0, j + 1 - w - off * (h - 1 - icr)) :
max(0, j + 1 - off * (h - 1 - icr))
] == ones[:w]
for icr, cr in enumerate(grid[max(0, i + 1 - h) : i + 1])
)
], key = lambda e: e[0] * e[1])
for j in range(c)
]
for i in range(r)
]
mas.append(ma)
ma = None
# ----------------- Checking Correctness and Printing Results -----------------
if check:
# Check that we have same answers for all algorithms
masx = [[[cma[ii][jj][0] * cma[ii][jj][1] for jj in range(c)] for ii in range(r)] for cma in mas]
assert all([masx[0] == e for e in masx[1:]]), 'Maximums of algorithms differ!\n\n' + sgrid + '\n\n' + (
'\n\n'.join(['\n'.join([' '.join([str(e1).rjust(2) for e1 in e0]) for e0 in cma]) for cma in masx])
)
ma = mas[0 if not check else algo]
if print_:
cchars = ['.'] + [chr(ii) for ii in range(ord('B'), ord('Z') + 1)] # These chars are used to show clusters from largest to smallest
res = [[grid[ii][jj] for jj in range(c)] for ii in range(r)]
mac = [[ma[ii][jj] for jj in range(c)] for ii in range(r)]
processed = set()
sid = 0
for it in range(r * c):
sma = sorted(
[(mac[ii][jj] or (0, 0, 0)) + (ii, jj) for ii in range(r) for jj in range(c) if (ii, jj) not in processed],
key = lambda e: e[0] * e[1], reverse = True
)
if len(sma) == 0 or sma[0][0] * sma[0][1] <= 0:
break
maxv = sma[0]
if it == 0:
maxvf = maxv
processed.add((maxv[3], maxv[4]))
show = True
for trial in [True, False]:
for i in range(maxv[3] - maxv[0] + 1, maxv[3] + 1):
for j in range(maxv[4] - maxv[1] + 1 - (maxv[3] - i) * maxv[2], maxv[4] + 1 - (maxv[3] - i) * maxv[2]):
if trial:
if mac[i][j] is None:
show = False
break
elif show:
res[i][j] = cchars[sid]
mac[i][j] = None
if show:
sid += 1
if not show_non_max and it == 0:
break
res = '\n'.join([''.join([str(res[ii][jj]) for jj in range(c)]) for ii in range(r)])
print(
'Max:\nArea: ', maxvf[0] * maxvf[1], '\nSize Row,Col: ', (maxvf[0], maxvf[1]),
'\nLowerRight Row,Col: ', (maxvf[3], maxvf[4]), '\nAngle: ', ("-1", " 0", "+1")[maxvf[2] + 1], '\n', sep = ''
)
print(res)
if debug:
# Print all computed maximums, for debug purposes
for cma in [ma, mac]:
print('\n' + '\n'.join([' '.join([f'({e0[0]}, {e0[1]}, {("-1", " 0", "+1")[e0[2] + 1]})' for e0_ in e for e0 in (e0_ or ('-', '-', 0),)]) for e in cma]))
print(end = '-' * 28 + '\n')
return ma
# ----------------- Testing -----------------
def test():
# Iterating over text inputs or other ways of producing inputs
for s in [
"""
1 1 0 0 0 1 0 1
1 1 1 0 1 1 1 1
1 0 0 0 1 0 1 1
0 0 1 0 1 0 1 1
1 1 1 1 0 0 1 1
0 0 1 1 1 1 1 0
0 1 0 0 1 0 1 1
""",
"""
1 0 1 1 0 1 0 0
0 1 1 0 1 0 0 1
1 1 0 0 0 0 0 1
0 1 1 1 0 1 0 1
0 1 1 1 1 0 1 1
1 1 0 0 0 1 0 0
0 1 1 1 0 1 0 1
""",
"""
0 1 1 0 1 0 1 1
0 0 1 1 0 0 0 1
0 0 0 1 1 0 1 0
1 1 0 0 1 1 1 0
0 1 1 0 0 1 1 0
0 0 1 0 1 0 1 1
1 0 0 1 0 0 0 0
0 1 1 0 1 1 0 0
"""
]:
solve(s, text = True)
if __name__ == '__main__':
test()
輸出：
Max:
Area: 8
Size Row,Col: (4, 2)
LowerRight Row,Col: (4, 7)
Angle: 0
CC000101
CC1011..
100010..
001010..
1BBB00..
00BBBDD0
010010DD
----------------------------
Max:
Area: 6
Size Row,Col: (3, 2)
LowerRight Row,Col: (2, 1)
Angle: -1
10..0100
0..01001
..000001
0BBB0101
0BBB1011
CC000100
0CC10101
----------------------------
Max:
Area: 12
Size Row,Col: (6, 2)
LowerRight Row,Col: (5, 7)
Angle: +1
0..01011
00..0001
000..010
BB00..10
0BB00..0
001010..
10010000
01101100
----------------------------
添加回答
舉報
0/150
提交
取消