Проблема



«SW Expert Academy
SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!www.swcompertamy



Есть массив N*N. 1 означает ядро ​​(процессор). 0 означает пустой. Красная линия - питание. Нам нужно подключить как можно больше ядер к блоку питания. Если мы соединили максимально возможное количество жил, нам нужно найти минимальную длину провода. Провода не могут пересекаться друг с другом, а могут быть соединены только по прямой линии. Предполагается, что жилы на краю (красный) подключены к источнику питания.

Входы

количество входных матриц

размер входной матрицы

входная матрица.

ex)

2
7
0 0 1 0 0 0 0
0 0 1 0 0 0 0
0 0 0 0 0 1 0
0 0 0 0 0 0 0
1 1 0 1 0 0 0
0 1 0 0 0 0 0
0 0 0 0 0 0 0
9
0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0
0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0
0 0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 1

вывод

#test_case минимальная_длина_провода

ex)

#1 12
#2 10

Идея

Алгоритмы Поиск в глубину + Обратный поиск

  • DFS (поиск в глубину)

Мы должны искать все соединительные случаи. Поэтому нам нужно использовать алгоритмы поиска в глубину. Мы будем искать каждую жилу для подключения 4 направлений и не подключать корпус. И мы будем искать следующее ядро ​​по каждому предыдущему кейсу!

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

  • Обратное отслеживание: как сделать это быстрее?

Во-первых, сократить количество кандидатов!

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

То есть время выполнения составляет 5 ^ (количество ядер).

Поэтому нам нужно уменьшить количество ядер. Нам не нужно искать ядро ​​на краю. Ядро на границе уже подключено!

Во-вторых, используйте алгоритмы поиска с возвратом!

Приоритетом этой проблемы является количество подключенных ядер. И минимальная длина провода является следующим приоритетом. Если максимальное количество ядер, которое можно подключить во время поиска, меньше максимального количества ядер, найденных ранее, дальнейший поиск не требуется. Просто вернись; это!

Это мой код.

Спасибо за чтение.