Входные данные: input.txt Выходные данные: output.txt Время на тест: 1 секунда Тесты к задаче:Скачать Автор задачи: Метельский И.С.
Карта местности задана квадратной таблицей A из N ( 1 <= N <= 3000 ) строк и N столбцов. Причем элемент Aij = 0, если клетка, находящаяся на пересечении i-й строки и j-го столбца свободна (проходима) и Aij = 1 в противном случае. Робот может перемещаться только по свободным клеткам, не может выходить за границы карты и из данной клетки может пройти за один ход в одну из четырех соседних (вверх, вниз, влево, вправо, если они свободны). Назовем путем из клетки Aab в клетку Acd такую последовательность корректных ходов робота, выполнив которую он, начиная из клетки Aab придет в клетку Acd, причем ни одну клетку не посетит два раза. Карта местности такова, что между любыми двумя свободными клетками существует хотя бы один путь. Назовем карту лабиринтом, если между любыми двумя свободными клетками существует ровно один путь.
Например,
- лабиринт, а
- нет.
Задание. По введенному числу N и квадратной таблице A размера N*N определить, является ли карта местности, определяемая таблицей А лабиринтом.
Входные данные. Ввод должен производиться из файла "Input.Txt". Первая строка этого файла содержит число N. Следующие N строк содержат по N символов каждая. J-й символ в i-й строке равен "0", если Aij = 0 и равен "1", если Aij = 1.
Выходные данные. Выведите в файл "Output.Txt" слово "Yes", если карта местности является лабиринтом и "No" в противном случае.