二維網格的洪水填充

Question

作爲一個遊戲的一部分，我正在構建一個2D網格，我需要找出網格上的兩個物體是否連接。有例如陷阱和牆壁阻塞了路，所以基本上我得到了網格的不同部分除以牆壁和陷阱，所以我從網格上的點P開始填充網格以找出哪些點屬於與體育

這裏同部分就是代碼基本上沒有：

1）建立一個基於輸入文件（作品）

2）電網找到起點P（作品）

3）來自P的填充（不工作）

4）打印網格檢查是否正確（工作）

網格建好了，起點也找到了，但是填充功能不起作用。有任何想法嗎？

例輸入文件：

7 9 
####### 
#..#G.# 
#...TG# 
#.....# 
#...G.# 
#...#.# 
###.P.# 
#G#.TG# 
####### 

（更新工程確定現在）運行與該代碼打印如下：

Start point at: [4, 6] (i.e. in grid[6][4]) 
[0, '#'][2, '#'][2, '#'][0, '#'][2, '#'][2, '#'][0, '#'] 
[2, '#'][1, '.'][1, '.'][2, '#'][1, 'G'][1, '.'][2, '#'] 
[2, '#'][1, '.'][1, '.'][1, '.'][2, 'T'][1, 'G'][2, '#'] 
[2, '#'][1, '.'][1, '.'][1, '.'][1, '.'][1, '.'][2, '#'] 
[2, '#'][1, '.'][1, '.'][1, '.'][1, 'G'][1, '.'][2, '#'] 
[2, '#'][1, '.'][1, '.'][1, '.'][2, '#'][1, '.'][2, '#'] 
[0, '#'][2, '#'][2, '#'][1, '.'][1, 'P'][1, '.'][2, '#'] 
[0, '#'][0, 'G'][2, '#'][1, '.'][2, 'T'][1, 'G'][2, '#'] 
[0, '#'][0, '#'][0, '#'][2, '#'][0, '#'][2, '#'][0, '#'] 

（更新正常工作）而這裏的代碼本身：

if __name__ == "__main__": 

    class Node: 
    UNEXPLORED = 0 
    CONNECTED = 1 
    VISITED = 2 

    def __init__(self, x, y, value): 
     self.x = x 
     self.y = y 
     self.state = Node.UNEXPLORED 
     self.value = value 

    def neighbor_with(self, node): 
     x_dist = abs(self.x - node.x) 
     y_dist = abs(self.y - node.y) 
     if x_dist == 1 and y_dist == 0: 
     return True 
     elif x_dist == 0 and y_dist == 1: 
     return True 
     else: 
     return False 

    def trap_or_wall(self): 
     if self.value == "T" or self.value == "#": 
     return True 
     else: 
     return False 

    def __str__(self): 
     return str([self.state,self.value]) 



    with open('in1.txt', 'r') as f: 

    row = f.readline() 
    dimensions = row.split(" ") 
    w = int(dimensions[0]) 
    h = int(dimensions[1]) 

    grid = [[Node(j,i, None) for i in range(w)] for j in range(h)] 

    #set grid 
    for i in range(h): 
     row = f.readline() 
     for j in range(w): 
     grid[i][j].value = row[j] 

    #find P 
    p = [] 
    for i in range(h): 
     for j in range(w): 
     if grid[i][j].value == "P": 
      p = [grid[i][j].y, grid[i][j].x] 
    print("Start point at: {:} (i.e. in grid[{:}][{:}])".format(p,p[1],p[0])) 

    #define function to flood fill the connected part 
    def fill_connected(matrix, node): 
     if node.state == Node.UNEXPLORED: 
     node.state = Node.VISITED 
     if not node.trap_or_wall(): 
      node.state = Node.CONNECTED 
      #recursively for neighbors 
      for i in range(h): 
      for j in range(w): 
       if matrix[i][j].neighbor_with(node): 
       fill_connected(matrix, grid[i][j]) 

    #flood fill from P 
    fill_connected(grid, grid[p[1]][p[0]]) 

    #check grid, i.e. print it 
    for i in range(h): 
     for j in range(w): 
     print(grid[i][j], end="") 
     print("\n", end="") 
    print() 

編輯：

我更新了代碼以解決座標順序錯誤，x = 4和y = 6現在應該是grid [6] [4]。之後我修復了其他錯誤，但我仍然不明白一件事：在洪泛填充函數定義的最後一行，爲什麼它必須是grid [i] [j]而不是grid [j] [i ]？後者產生超出範圍的錯誤。

Answer 1

你搞亂了座標的順序。幾乎在任何地方都使用網格（Y，X），除了填充函數。看到最初的呼叫：你在x = 4時發現y = 6，這就是i = 6 j = 4。然後你調用fill_connected（4,6）。這是右牆的一點。

我只會在列表索引上工作，如果沒有足夠的理由給額外的座標。