print1654. Приключения на шахматной доске

printПриключения на шахматной доске

Ограничения: время – 2s/4s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Ваня очень любит шахматы. Причем он не только любит просто играть в шахматы, но часто придумывает разные головоломки и просто забавные задачки с использованием шахматных фигур. Также вместо стандартной шахматной доски `8\ times\ 8` Ваня часто использует в своих задачах доски другого размера.
Недавно он придумал новую головоломку и рассказал ее своим друзьям. Суть головоломки заключается в следующем. На одно из полей доски размером `m\ times\ n` записывается некоторое положительное целое число и затем на него ставится ферзь.
После этого Ваня делает `k` ходов ферзем, каждый раз перемещая его по шахматным правилам на одно из полей, на котором он еще не был. При этом каждый раз, перед тем как поставить ферзя на некоторое поле, он записывает на это поле целое число, причем это число всегда больше всех чисел, уже записанных на доске.
Задача друзей Вани — по числам, записанным на доске, восстановить маршрут ферзя или выяснить, что Ваня где-то ошибся. Поскольку Ваня часто выбирает достаточно большие `m`, `n` и `k`, друзья устали решать эту головоломку вручную и решили написать для ее решения программу. Помогите им!
Напомним, что по шахматным правилам ферзь может пойти на любое поле доски, находящееся на одной вертикали, горизонтали или диагонали с тем полем, на котором он находится.
Ввод
Первая строка входного файла содержит числа `m`, `n` и `k` (`1\ ≤\ m,\ n\ ≤\ 300`, `0\ ≤\ k\ <\ "mn"`). Следующие `m` строк содержат по `n` целых чисел и описывают поля доски, пустому полю соответствует число 0, а полю, на котором записано число — это число. Все числа, записанные на доске, положительные, целые и не превышают `10^9`.
Ввод
Если Ваня ошибся при построении головоломки, выведите в выходной файл сообщение "Wrong Board".
В противном случае выведите `m` строк по `n` чисел — для каждого поля выведите номер хода, перед которым ферзь побывал на этом поле, а для последнего поля, на котором он побывал — число `k+1`. Для полей, на которых ферзь не побывал, выведите число 0.

Пример ввода 1

4 4 7
10 20 0 100
30 0 0 40
0 0 0 0
45 42 0 70

Пример вывода 1

1 2 0 8
3 0 0 4
0 0 0 0
6 5 0 7

Пример ввода 2

2 4 4
10 20 30 40
0 50 0 0

Пример вывода 2

Wrong Board

Пример ввода 3

2 2 2
1 2
4 3

Пример вывода 3

Wrong Board
Источник: V Всероссийская командная олимпиада школьников по программированию, 2004
loading