Республиканская олимпиада по информатике, 2011 год, 10-11 классы

Задача B. Ферзи

Ограничение по времени:

2 секунды

Ограничение по памяти:

256 мегабайта

На шахматной доске $N \times N$ написаны числа — по одному на каждой ячейке. Расставьте $N$ ферзей так, чтобы они не били друг друга (один ферзь бьет другого, если они стоят на одной горизонтали, вертикали или диагонали) и чтобы сумма чисел на занятых ячейках была максимально возможной.

Формат входного файла

Первая строка входного файла содержит одно целое число $N$ $(1 \le N \le 15).$ Каждая из следующих $N$ строк содержит по $N$ неотрицательных целых чисел, не превышающих 1000, — описание доски. Числа в строках разделены пробелами.

Формат выходного файла

Выходной файл должен содержать ровно $N$ строк по $N$ чисел в каждой. $j$-е число $i$-й строки должно быть 1, если в ячейке $(i, j)$ стоит ферзь, и 0 в противном случае.

Примеры:

Вход

4
1 2 1 1
1 1 1 1
1 1 1 1
1 1 1 1

Ответ

0 1 0 0
0 0 0 1
1 0 0 0
0 0 1 0