Задача Король и Ферзь (KING)
На квадратной доске размером 8*8 клеток расположены две фигуры: ферзь и король и некоторое количество шашек. Ферзь и король двигаются поочередно (ферзь начинает первым), шашки остаются неподвижными. Король может ходить на соседнее по горизонтали, вертикали или диагонали свободное поле. Ферзь может ходить по горизонтали, вертикали или диагонали, но не может перепрыгивать через шашки или становиться на поле, занятое шашкой. Фигура выигрывает, если своим последним ходом она занимает поле, занятое другой фигурой (сбивает фигуру).
Нужно определить, за какое число ходов игра закончится и какая фигура выиграет, если считать, что обе фигуры ходят оптимально и стремятся ускорить выигрыш или отстрочить проигрыш.
Напишите программу KING, которая читает с клавиатуры 8*8 чисел Tij описывающих конфигурацию доски (Tij = 0, если поле (i,j) свободно; Tij = 1, если на поле (i,j) находится шашка; Tij = 2, если на поле (i,j) стоит ферзь; Tij = 3, если на поле (i,j) стоит король) и выводит на экран результат партии - целое число X (X равняется числу ходов обеих фигур, если выигрывает ферзь; X равняется числу ходов обеих фигур, если выигрывает король; X = 0 , если партия никогда не закончится).
Формат ввода/вывода:
Ввод:
T11
T12
...
T18
T21
T22
...
T28
... ... ... ...
T81
T82
...
T88
| Вывод:
X
|
Пример:
Ввод:
0 0 0 0 0 2 1 1
1 0 0 0 0 1 0 1
0 0 0 0 1 0 0 1
0 0 0 1 0 0 0 1
1 0 1 0 0 0 0 1
0 1 0 0 0 0 0 1
1 0 1 0 0 0 0 1
0 3 0 0 0 0 0 1
|
Вывод:
5
|
|
