Codeforces Round 644 (Div. 3) |
---|
Закончено |
Полигон — это не только лучшая платформа для разработки задач, но и квадратная матрица со стороной $$$n$$$, изначально состоящая из нулей.
На полигоне проводятся боевые учения. Поэтому над каждой клеткой в первой строке и слева от каждой клетки первого столбца находится пушка. Таким образом, всего есть $$$2n$$$ пушек.
Пушки стреляют единицами. В один момент времени стреляет не больше одной пушки. Когда единица вылетает из пушки, то она летит вперед, по направлению выстрела, до тех пор, пока не столкнется с границей полигона или другой единицей. После этого она занимает клетку, в которой находилась перед столкновением, и остается там. Изучите примеры для лучшего понимания.
Более формально:
Например, рассмотрим следующую последовательность выстрелов:
1. Стреляет пушка в строке $$$2$$$. 2. Стреляет пушка в строке $$$2$$$. 3. Стреляет пушка в столбце $$$3$$$.
У вас на столе лежит отчет с проведенных учений. Этот отчет является квадратной матрицей с длиной стороны $$$n$$$, состоящей из нулей и единиц. Вам интересно, действительно ли произошли учения. Другими словами, существует ли такая последовательность выстрелов, что в конце получится заданная матрица?
Каждая пушка может сделать произвольное количество выстрелов. Перед началом учений полигон состоит из нулей.
В первой строке записано целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов тестовых данных в тесте. Далее следуют $$$t$$$ наборов тестовых данных.
Каждый набор начинается со строки, в которой записано целое число $$$n$$$ ($$$1 \le n \le 50$$$) — размер полигона.
Далее следуют $$$n$$$ строк длины $$$n$$$, состоящих из нулей и единиц — матрица полигона после проведения учений.
Суммарная площадь матриц во всех наборах тестовых данных в одном тесте не превосходит $$$10^5$$$.
Для каждого набора тестовых данных выведите:
Буквы в словах YES и NO можно выводить в любом регистре.
5 4 0010 0011 0000 0000 2 10 01 2 00 00 4 0101 1111 0101 0111 4 0100 1110 0101 0111
YES NO YES YES NO
Первый набор тестовых данных примера разобран в условии.
Ответ на второй набор NO, так как, вылетев из любой пушки, единица в клетке ($$$1, 1$$$) продолжила бы свой полет дальше.
Название |
---|