Взрывчатка
(Время: 1 сек. Память: 16 Мб Сложность: 44%)
На территории базы противника расположены N арсеналов, которые нужно уничтожить. Вы, Агент-070, имеете запас взрывчатки, достаточный для того, чтобы взорвать все N арсеналов по одному. Но при этом велик риск обнаружения.
Однако Вам известно, что при взрыве каждого арсенала создаётся взрывная волна, которая может достичь других арсеналов и спровоцировать их взрыв. Эти арсеналы тоже будут создавать свои взрывные волны. В Центре вам выдали таблицу, в которой для каждого арсенала указано, какие другие арсеналы попадут под его взрывную волну.
Так как на минирование одного арсенала требуется время, а оно очень дорого, Вам нужно заминировать как можно меньше арсеналов, чтобы, взорвав их, гарантированно уничтожить все арсеналы на базе.
Входные данные
В первой строке входного файла INPUT.TXT содержится число N – количество арсеналов на территории базы (1 ≤ N ≤ 100).
Далее дана таблица отношений: в N строках содержится по N символов, j-ый символ i-ой строки равен «1», если при взрыве i-го арсенала j-ый попадёт под его взрывную волну и «0» иначе.
Выходные данные
В выходной файл OUTPUT.TXT выведите одно число – минимальное количество арсеналов, которое требуется заминировать для уничтожения всех арсеналов на базе.
Примеры
№ | INPUT.TXT | OUTPUT.TXT |
1 | 3
000
100
100 | 2 |
2 | 3
010
001
000 | 1 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
|