Требуется выполнить обход прямоугольного поля, перемещаясь в нём по правилам шахматного коня. Начальная позиция коня определена. Необходимо посетить все клетки без повторных заходов. Гарантируется, что такой обход возможен.
В первой строке входного файла INPUT.TXT содержится два натуральных числа N и M – размеры поля (6 ≤ N, M ≤ 100). Далее следует карта поля: N строк по M символов в каждой строке. Символом «.» (точка) обозначается пустое пространство, начальная позиция коня задаётся единственным в поле символом «K» (заглавная буква английского алфавита).
В выходной файл OUTPUT.TXT выведите матрицу обхода поля, в каждой ячейке которого должен быть вписан номер шага её посещения (начиная с единицы). Числа следует разделять пробелами, допускается использовать лишние пробелы. В случае неоднозначного решения следует вывести любое.
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 8 8
K.......
........
........
........
........
........
........
........ | 1 16 27 22 3 18 47 54
26 23 2 17 46 55 4 19
15 28 25 50 21 48 53 56
24 35 30 45 58 51 20 5
29 14 59 34 49 44 57 52
36 31 38 41 60 63 6 9
13 40 33 62 11 8 43 64
32 37 12 39 42 61 10 7 |
