查找而不塊最大覆蓋元件通過障礙通路

Question

鑑於MXN矩陣，其中矩陣元素是「」。要麼 」*」。哪裏。代表道路，*代表街區或牆壁。人可以向前，向下和對角移動，我們需要找到最大的「。」。被人遮住而不被牆擋住。 Example(in image)

能否請你建議我有效的算法來解決這個問題？

Answer 1

你必須這樣做：https://en.wikipedia.org/wiki/Flood_fill 拿你能做的最大的洪水。

1. 你通過你的矩陣，找到'。'
2. 從這一點開始做洪水。您將該區域氾濫的元素數量與您已經找到的最大值進行比較。爲了使這一點變得容易，你可以用一個字母或數字或任何你想要的東西洪水氾濫，而不是用'。'。你添加的是什麼，而不是'。'將其視爲牆或'*'，因此您不會一次又一次地氾濫該區域。
3. 繼續經過矩陣，並試圖尋找下一個「」。以前的所有'。'在那裏淹水，所以你不會考慮同一地區兩次。
4. 重做2，直到你找不到任何更多的「」。最大值將包含您的答案。
5. 當您有答案時，您可以返回Matrix，並且您已經知道該字母或數字以最大的結果淹沒該區域，因此您可以打印最大的區域。

Answer 2

您是否在尋找確切的路徑或僅病例數？

編輯：這裏它創建了一個隨機矩陣並計算你的「牆」定義每個區域的案件數量smallp Python腳本。

import numpy as np 

matrix = np.random.randint(2, size=(10, 10)) 
print(matrix) 
M, N = matrix.shape 

walked = [] 
zonesCount = [] 


def pathCount(x, y): 
    if x < 0 or y < 0 or x >= M or y >= N: 
     return 0 
    if matrix[x, y] == 1: # I replaced * by 1 and . by 0 for easier generation 
     return 0 
    if (x, y) in walked: 
     return 0 

    walked.append((x, y)) 

    count = 1 

    for i in [x - 1, x, x + 1]: 
     for j in [y - 1, y, y + 1]: 
      if (i, j) != (x, y): 
       count += pathCount(i, j) 

    return count 

for x in range(M): 
    for y in range(N): 
     if not (x, y) in walked: 
      zonesCount.append(pathCount(x, y)) 

print('Max zone count :', max(zonesCount)) 

這裏是結果：

[[0 0 1 0 0 0 1 0 1 0] 
[1 0 1 0 0 0 1 0 1 1] 
[0 1 0 0 1 0 0 1 1 1] 
[0 0 1 0 0 0 1 1 0 1] 
[1 0 1 1 1 1 0 1 1 0] 
[1 0 1 1 1 1 0 1 1 0] 
[0 0 0 1 1 1 0 0 0 0] 
[1 0 0 1 1 0 0 1 1 0] 
[0 1 0 1 0 0 1 0 1 1] 
[0 1 1 0 0 0 1 0 1 0]] 
Max zone count : 50