Задача . E. Полигон

Полигон — это не только лучшая платформа для разработки задач, но и квадратная матрица со стороной \(n\), изначально состоящая из нулей.

На полигоне проводятся боевые учения. Поэтому над каждой клеткой в первой строке и слева от каждой клетки первого столбца находится пушка. Таким образом, всего есть \(2n\) пушек.

Изначальный полигон для \(n=4\).

Пушки стреляют единицами. В один момент времени стреляет не больше одной пушки. Когда единица вылетает из пушки, то она летит вперед, по направлению выстрела, до тех пор, пока не столкнется с границей полигона или другой единицей. После этого она занимает клетку, в которой находилась перед столкновением, и остается там. Изучите примеры для лучшего понимания.

Более формально:

• если пушка, стоящая в строке \(i\) перед первым столбцом, стреляет единицей, то единица начинает свой полет из клетки (\(i, 1\)) и заканчивает в какой-то клетке (\(i, j\));
• если пушка, стоящая в столбце \(j\) над первой строкой, стреляет единицей, то единица начинает свой полет из клетки (\(1, j\)) и заканчивает в какой-то клетке (\(i, j\)).

Например, рассмотрим следующую последовательность выстрелов:

1. Стреляет пушка в строке \(2\).                         2. Стреляет пушка в строке \(2\).                         3. Стреляет пушка в столбце \(3\).

У вас на столе лежит отчет с проведенных учений. Этот отчет является квадратной матрицей с длиной стороны \(n\), состоящей из нулей и единиц. Вам интересно, действительно ли произошли учения. Другими словами, существует ли такая последовательность выстрелов, что в конце получится заданная матрица?

Каждая пушка может сделать произвольное количество выстрелов. Перед началом учений полигон состоит из нулей.