Это проблема, состоящая из двух частей, о которой я подумал.
Постановка задачи:
В поле n по прямоугольнику angular есть грабитель R и два полицейских C1 и С2. Каждый из трех начинается с некоторого начального квадрата, и в начале погони R, C1, C2 все знают позиции друг друга.
R делает первый ход, затем C1 и C2. Они могут двигаться только вверх, вниз, влево или вправо. Некоторые квадраты недоступны, потому что есть препятствие. Если C1 или C2 достигают квадрата, в котором находится R, то они ловят R.
Чтобы убежать, R должен достичь квадрата X по периметру сетки. Если R достигает квадрата X до того, как его поймают C1 или C2, то R успешно убегает. Иначе, R не может сбежать.
В качестве входных данных мы предоставляем: значения m (количество строк) и n (количество столбцов), начальные координаты для R, C1, C2 и список недоступных квадраты.
I) Используя предоставленные данные, как вы можете использовать список смежности для построения графа для решения проблемы. Проанализируйте время выполнения создания графа.
Я действительно думал об использовании матрицы смежности из-за представления сетки, но нас просят использовать и список смежности. В результате я запутался в том, что следует считать вершиной и ребром в этой задаче. Я думал, что каждый квадрат в сетке будет вершиной, а его ребра будут всеми соседними квадратами, по крайней мере, теми, которые он может достичь, 4 квадрата - максимум. Так должен ли мой список смежности хранить ВСЕ m по n парам, а затем для каждой пары поддерживать связанный список соседей, то есть квадратов, достижимых? Если бы я пошел по этому маршруту, то было бы (m * n) вершин, и затем для каждого из них мне пришлось бы проверить, какие квадраты достижимы (вверх, вниз, влево, вправо) и является ли этот квадрат недоступным, поэтому я бы должны просмотреть список недоступных, представленный в качестве входных данных, что займет O (n) времени. Так что я думаю, что это дало бы мне время O (m * n) для создания графа. Могу ли я сделать лучше, чем это?
II) Учитывая график, который вы создаете в части (I), опишите алгоритм, чтобы проверить, может ли R убежать.
* Предположение: стратегия, которая R, C1 и C2 незначительный. Неважно, если R, C1, C2 движутся «умным» или совершенно случайным образом.
Поскольку R объявляет свое место назначения до того, как начнется погоня, я думаю, что это просто вопрос того, существует ли путь от где R начинается с его целевой площади. Так можно ли мне запустить DFS и проверить, может ли R добраться до места назначения? Но я не знаю, что R сможет избежать C1 и C2.
Руководство ценится.