Человеческий матрикс превращается в зомби

Question

Я встречаюсь с этим поиском в интервью. Пожалуйста, дайте мне знать ответ на этот квест.

У нас есть матрица, такая как 3 X 3, 5 X 5 или 7 X 7. В середине мы имеем X (представляем зомби) и 0 (пустое или пустое) или 1 (Человек) на всех узлах. Х создал все смежные человеческие узлы зомби через минуту. Итак, сколько времени потребуется для создания всех матричных зомби.

Answer 1

Не позволяйте терминологии обмануть вас: это проблема графа. Я предполагаю, что зомби также может достичь людей, которые по диагонали примыкают к нему.

Если вы проведете Breadth первый поиск из «точки зомби», вы сможете определить это время (если оно существует). Это в основном, как вы приступите: (пример кода в 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 

Поиски гипотетических выживших остается в качестве упражнения.