Дана матрица размера \(n \times n\), состоящая из 0 и 1. Строки матрицы пронумерованы от \(1\) до \(n\) сверху вниз, столбцы пронумерованы от \(1\) до \(n\) слева направо. Клетку на пересечении \(x\)-й строки и \(y\)-го столбца обозначим как \((x, y)\).
AquaMoon хочет превратить все элементы матрицы в 0. За один шаг она может выполнить следующую операцию:
- выбрать произвольную клетку, пусть это \((i, j)\), затем инвертировать элемент в клетке \((i, j)\), а также инвертировать все элементы в клетках \((x, y)\), для которых \(x > i\) и \(x - i \ge \left|y - j\right|\). Инвертирование — это замена символа на противоположный: 0 на 1, 1 на 0.
Помогите AquaMoon определить наименьшее число шагов, необходимых для того, чтобы превратить все элементы матрицы в 0. Можно показать, что ответ всегда существует.
Выходные данные
Для каждого набора входных данных выведите наименьшее необходимое число шагов.
Примечание
В первом наборе входных данных можно действовать так:
- выполнить операцию для клетки \((1, 3)\).
Очевидно, изначально не все элементы матрицы равны 0, так что необходима как минимум одна операция. Значит, \(1\) и есть ответ.
В втором наборе входных данных можно действовать так:
- выполнить операцию для клетки \((3, 3)\);
- выполнить операцию для клетки \((1, 1)\).
Можно показать, что невозможно превратить все элементы в 0 за \(0\) шагов или за \(1\) шаг, так что ответ равен \(2\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
5
00100
01110
11111
11111
11111
3
100
110
110
6
010101
111101
011110
000000
111010
001110
|
1
2
15
|