В соревновательном соревновании по программированию возникает вопрос, будет ли узел доступен из начальной точки с изменением закрытых путей.
Грабителю придется путешествовать из города х в городy на пути, так что в городе, куда он направится, не будет полицейского и соседних узлов с полицейским (тоже между ними).Каждый день он должен менять город, в котором он стоит, иначе его поймают, даже если в этом городе нет работающего полицейского.
Условие: в первый день грабитель никогда не будет пойман, даже если полицейскийв городе, в котором он присутствует, или в соседнем городе с городом, где есть офицер полиции.
Выходными данными должно быть минимальное количество дней, чтобы грабитель достиг города назначения или «УДЕРЖИЛ», если он получитвсе равно поймали.
Пример 1: узел источника равен 1, а узел назначения равен 2
Двунаправленные ребра:
1 2
5 2
4 1
3 4
5 6
2 3
Количество дней месяца 6
день 1: полицияв городе 3
день 2: полиция в городе 2
день 3: полиция в городе 1
день 4: полиция в городе 2
день 5: полиция в городе 1
день 6: полиция в городе 4
(этот шаблон будет повторяться, когда закончится каждый месяц)
Вывод5
Пример 2: узел источника равен 1, а узел назначения - 7
Двунаправленные ребра:
1 2
1 3
1 4
3 5
4 5
2 6
5 7
6 7
3 6
Количество дней месяца: 2
день 1: полиция в городе 2
день 2: полиция в городе 5
Выходные данные: "CAUGHT"
У меня есть тЯ решил создать эту проблему в виде графика, в котором я буду циклически проходить по узлам в каждом случае, чтобы достичь места назначения, однако я не знаю, как обнаружить «CAUGHT» в случае бесконечного цикла.
Anyбыла бы признательна за помощь.