ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Соревнование школьников. Октябрь 2006

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

I. Разрезание квадрата

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Вася после того, как сделает все уроки, развлекается следующей головоломкой. Он берёт белый клетчатый лист размером N × N клеток, выбирает из него некоторое непустое связное подмножество клеток и красит это подмножество в чёрный цвет. После того, как Вася вырезает из листа чёрный кусок, остаётся ровно один белый кусок. Затем Вася совмещает куски в первоначальный квадрат и кладёт на бесконечный плоский стол. Задача Васи — разделить куски, то есть удалить один из кусков на большое расстояние от другого, не отрывая ни один из кусков от поверхности стола. Например, на рисунке заданы квадраты 5 × 5. В первом случае куски можно разделить, во втором — нельзя.
Problem illustration
Однажды к Васе в гости пришел Петя. Увидев, чем занимается Вася, Петя решил помочь лучшему другу и написать программу, которая определяет, можно ли разделить белую и чёрную части.

Исходные данные

В первой строке записано целое число N (3 ≤ N ≤ 1000). В следующих N строках по N символов в каждой приведена раскраска листа. Символы 0 обозначают белую часть, а 1 — чёрную. Гарантируется, что оба куска связны по сторонам (например, два квадрата с общей вершиной, но без общей стороны, не считаются связным куском).

Результат

Выведите «Yes», если части можно разделить, и «No» в противном случае.

Примеры

исходные данныерезультат
5
10001
10001
10001
11111
11111
Yes
5
11011
11011
10001
11111
11111
No
Автор задачи: Александр Торопов
Источник задачи: XIII командный чемпионат школьников Свердловской области по программированию (14 октября 2006 года)
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1497. Разрезание квадрата