人間のマトリックスがゾンビに変換

Question

私はインタビューでこのクエストに直面する。このクエストの可能な答えを教えてください。

3 X 3,5 X 5または7 X 7のような行列があります。中には、すべてのノードでX（ゾンビを表す）と0（空白または空白）または1（人間）があります。 Xは1分ですべての人間のノードのゾンビを作成しました。 すべてのマトリックスゾンビを作成するのにどれだけの時間がかかりますか？

Answer 1

これはグラフの問題です。私は、ゾンビがの対角線に隣接する人間に届くと仮定します。です。

あなたは「ゾンビ・ポイント」から幅優先探索を行った場合、あなたは（存在する場合）、その時間を決定することができるようになります。これは、あなたがどのように進める基本的には次のとおりです。（Pythonでのコードサンプル）

matrix = [['1', '0', '0'],['1', 'X', '1'],['0', '0', '0']] 
mid = len(matrix)//2 
yet_to_explore = [(mid,mid,0)] 
explored_set = {} # This is a hashset of explored nodes 
while [] != yet_to_explore: 
    cur_vertex = yet_to_explore.pop(0) 
    x = cur_vertex[0] 
    y = cur_vertex[1] 
    if (x,y) in explored_set: 
     continue 
    explored_set[(x,y)] = cur_vertex[2] 
    matrix[x][y] = 'X' 
    for i in range(-1,2): 
     if 0 > x + i or len(matrix) <= x + i: 
      continue 
     for j in range(-1,2): 
      if 0 > y + j or len(matrix) <= y + j: 
       continue 
      elif 0 == i and 0 == j: 
       continue 
      elif matrix[x+i][y+j]=='1': 
       yet_to_explore.append((x+i, y+j, cur_vertex[2]+1)) 
# If your matrix contains a '1' after the BFS this means some human were not reachable (they are isolated) -> the desired time does not exist since not every human can be a zombie 
# Else the time you are looking for is the following result: 
time = max(list(explored_set.values())) 

生存者あり例：架空の生存者のための

matrix = [['0', '0', '0', '0', '0', '0', '0'], 
      ['1', '1', '1', '1', '0', '0', '0'], # The human on the left will be contamined within 4 min 
      ['0', '0', '0', '1', '0', '0', '0'], 
      ['1', '0', '0', 'X', '0', '0', '0'], # The human on the left will survive 
      ['0', '0', '1', '0', '1', '0', '0'], 
      ['0', '0', '1', '0', '0', '1', '0'], 
      ['0', '1', '0', '0', '0', '0', '1']] # The human on the right will be contamined within 3 min 

検索が課題として残されています。