我正在嘗試編寫(xiě)一個(gè)函數(shù)，該函數(shù)獲取一組元組作為參數(shù)，并檢查給定的字符是否在NxN網(wǎng)格中形成連續(xù)形狀。元組是構(gòu)成網(wǎng)格的列表中的字符的索引。如果另一個(gè)字符的正下方、上方或側(cè)面有一個(gè)字符，則該形狀是連續(xù)的。continuous not continous not continous xxxxx xxxxx ooxxx xxoox xxoox xxxxx xxxoo ooxxx xxoox xxxoo oxxxx xxoox xxxxo xoxxx xxxxx ======================== def connected(characters): result = True for i in characters: if (i[0]+1, i[1]) in characters or (i[0]-1, i[1]) in characters or (i[0], i[1]+1) in characters or (i[0], i[1]-1) in characters: result = True characters.discard(i) else: result = False return result return result>>>connected({(1, 3), (2, 1), (2, 3), (0, 3), (1, 1)})將形成這種形狀，因此它不會(huì)是連續(xù)的，但我的代碼認(rèn)為它是連續(xù)的。xxxoxoxoxoxoxxxx這在大多數(shù)情況下都有效，但是當(dāng)給定的字符形成兩個(gè)單獨(dú)的連續(xù)形狀時(shí)不起作用，就像我上面給出的第二個(gè)錯(cuò)誤示例一樣。我試圖通過(guò)在檢查后刪除每個(gè)元組來(lái)解決此問(wèn)題，但我得到Traceback (most recent call last): File "C:/Users/User/PycharmProjects/untitled6/venv/1.py", line 47, in <module> connected({(1, 2), (1, 3), (2, 2), (0, 3), (0, 4)}) File "C:/Users/User/PycharmProjects/untitled6/venv/1.py", line 15, in connected for i in grid:RuntimeError: Set changed size during iteration錯(cuò)誤。我能做些什么來(lái)解決這個(gè)問(wèn)題？
1 回答
森欄
TA貢獻(xiàn)1810條經(jīng)驗(yàn) 獲得超5個(gè)贊
有關(guān)錯(cuò)誤的詳細(xì)信息，請(qǐng)參閱 https://stackoverflow.com/a/38423075。基本上，如果要在循環(huán)中修改該集合，則必須循環(huán)訪問(wèn)該集合的副本。
除此之外，您的算法中還存在一個(gè)缺陷。
如果不丟棄當(dāng)前字符，則僅當(dāng)每個(gè)字符都有鄰居時(shí)才進(jìn)行檢查。這是可以的：
xxxxx
xoxox
xoxox
xxxxx
但是，如果您丟棄當(dāng)前字符，則可能會(huì)有以下情況：
xxx xxx
xox <- cur x x <- discarded
xox xox <- has no neighbor!
xxx xxx
經(jīng)典算法基于樹(shù)遍歷：從任何 not 開(kāi)始，遍歷所有直接鏈接的節(jié)點(diǎn)。如果看到所有節(jié)點(diǎn)，則圖形已連接。
我在這里使用DFS，但如果你愿意，你可以使用BFS：
def connected(characters):
seen = set()
stack = [next(iter(characters))] if characters else []
while stack:
c = stack.pop()
seen.add(c)
for other_c in [(c[0]+1, c[1]), (c[0]-1, c[1]), (c[0], c[1]+1), (c[0], c[1]-1)]:
if other_c not in seen and other_c in characters:
stack.append(other_c)
return not (characters - seen)
print(connected({(1, 3), (2, 1), (2, 3), (0, 3), (1, 1)}))
# False
print(connected({(1, 3), (2, 1), (2, 3), (0, 3), (1, 1), (1, 2)}))
# True
添加回答
舉報(bào)
0/150
提交
取消