Проверка наличия двух точек в логическом двумерном списке

Question

Есть ли какой-либо быстрый способ узнать, если две точки на двумерной булевой области подключены, и вы можете шагать только вверх, вниз, влево и вправо на квадрате со значением True? Допустим, вы бы следующие 6x6 2D список:

В коде, который был бы:

bool2DList = [6][6] 
bool2DList = { True, True, False, False, True, True, 
       False, True, True, False, True, True, 
       False, True, True, False, False, True, 
       False, False, False, False, False, True, 
       False, False, False, False, True, True, 
       False, True, True, True, True, True } 

Зеленые квадраты имеют значение Истинные и синие Ложные. Я думал о функции (она, вероятно, должна быть рекурсивной), в которую вы бы поместили 2D-список в качестве аргумента вместе со списком кортежей (координат) нескольких точек и окончательным одним кортежем специальной точки, он мог иметь заголовок например:

def FindWay(bool2DList,listOfPoints,specialPointCoord) 

В этом примере особой точкой будет точка P с координатами 5; 1. Представим себе, что вы начнете идти от этих особых точек. Какие моменты вы могли бы достичь, не наступая на синие квадраты? В этом примере только точки P4 и P5 (выход может быть обозначен координатами этих точек, поэтому 0; 5 и 5; 3). Это, вероятно, должно быть рекурсивным, но я понятия не имею, как должно выглядеть тело.

спасибо.

Answer 1

Я боюсь, что нет никакого тривиального способа сделать это. Это проблема обхода графика, и у Python нет встроенных функций, поддерживающих это. Я ожидаю, что вам понадобится простая реализация breadth-first graph search.

Вкратце, вы сохраняете список узлов, которые вы посещали, но не обрабатывались; другой список узлов, которые вы обработали. Шаги выглядеть следующим образом:

обрабатываются = [] посетил = [P] в то время посетил не пуст: удалить узел А из посещаемой списка для каждого узла B можно добраться непосредственно из A: если B - новый (не в списке посещенных или обработанных): положить B в список для посещения положить A в обработанный список

Это найдет все узлы, к которым вы можете добраться. Если вас беспокоит какой-то конкретный узел, то внутри цикла проверьте, является ли ваш целевой узел B. Когда вы положите B в список посещений, поставьте его на передний план для глубины - сначала, на спине для ширины.

В этом приложении «все узлы, которые вы можете достигнуть», состоят из граничащих с той же булевой меткой.

Answer 2

Вот вариант, как вы можете его код:

A = np.array([[0, 1, 1, 0], [1, 0, 1, 1], [1, 0, 1, 0], [0, 1, 0, 0]]).astype(bool) 
print A 

[[False True True False] 
[ True False True True] 
[ True False True False] 
[False True False False]] 

Мы можем обновить стандартную функцию DFS для наших нужд:

def dfs_area(A, start): 
    graph = {} 
    res = np.zeros_like(A) 
    for index, x in np.ndenumerate(A): 
     graph[index] = x 
    visited, stack = set(), [start] 

    while stack: 
     vertex = stack.pop() 
     x, y = vertex[0], vertex[1] 
     if vertex not in visited and graph[vertex] == True: 
      visited.add(vertex) 
      if x < A.shape[0]-1: 
       stack.append((x+1, y)) 
      if x > 1: 
       stack.append((x-1, y)) 
      if y < A.shape[1]-1: 
       stack.append((x, y+1)) 
      if y > 1: 
       stack.append((x, y-1)) 
    res[tuple(np.array(list(visited)).T)] = 1 

    return res 

Предположим, что мы хотим, чтобы пункты, связанные с (1, 2) - второй ряд, третье значение:

mask = dfs_area(A, (1,2)) 

>> mask 

array([[0, 1, 1, 0], 
     [0, 0, 1, 1], 
     [0, 0, 1, 0], 
     [0, 0, 0, 0]])