Определить в каком положении находится черный игрок: мат, пат или обычное положение

На экзамене по алгоритмам Петя вытащил несчастливую задачу, поэтому весьма просит вашей помощи. Перед вами стандартная шахматная доска 8×8, ячейки которой пронумерованы слева направо от a до h и снизу вверх от 1 до 8. Среди белых фигур доске могут быть все виды фигур, кроме короля, а среди черных наоборот есть только один король. Также известно, что фигуры расставлены абсолютно произвольно, то есть их размещение может не подчиняться стандартным правилам шахмат (белые даже могут иметь много фигур определенного типа). Ваша задача – определить, в каком положении находится черный игрок: мат, пат или обычное положение.

0

На экзамене по алгоритмам Петя вытащил несчастливую задачу, поэтому весьма просит вашей помощи. Перед вами стандартная шахматная доска 8×8, ячейки которой пронумерованы слева направо от a до h и снизу вверх от 1 до 8. Среди белых фигур доске могут быть все виды фигур, кроме короля, а среди черных наоборот есть только один король. Также известно, что фигуры расставлены абсолютно произвольно, то есть их размещение может не подчиняться стандартным правилам шахмат (белые даже могут иметь много фигур определенного типа). Ваша задача – определить, в каком положении находится черный игрок: мат, пат или обычное положение.

Справка по шахматам:
Шах — тактический ход, при котором будет проходить нападение на короля соперника.
Мат — ситуация, когда король оказывается под шахом, и у игрока нет никакого возможного хода, после которого король перестал бы находиться под шахом.
Пат — состояние, когда ходящая сторона не может это сделать, потому что все ее фигуры лишены возможности совершить ход, при этом король не находится под шахом.
Правила ударов/ходов фигур в рамках задания:
Королева бьет по вертикалям, диагоналям и горизонтали, на которых она находится, но она не может перепрыгивать через другие фигуры.
no title
Тура бьет по вертикалям и горизонтали, на которых она находится, но не может перепрыгивать через другие фигуры.
no title
Слон – бьет по диагоналям, на которых он находится, но не может перепрыгивать через другие фигуры.
no title
Лошадь - ход конем состоит из двух передвижений: на одно поле по вертикали или горизонтали, затем удаляясь от исходного поля на одно поле по диагонали. Это единственная фигура, которая может перепрыгивать через другие фигуры.
no title
Пешка – бьет по диагонали на одну ячейку в сторону соперника (таким образом белые пешки всегда бьют только по диагонали вверх).
no title
Король — передвигается со своего поля на одно из свободных смежных полей (в том числе и по диагонали), не находящегося под ударом фигур соперника. Может бить фигуру, находящуюся на смежном поле, если она не под ударом.
no title
Входные данные
Входные данные содержат 8 строк, каждая из которых состоит из 8 символов. Каждый символ задает соответствующую ячейку шахматной доски:
символ "." обозначает пустую клеточку
символ «p» обозначает пешку
символ «r» обозначает тура
символ «n» обозначает лошадь
символ «b» означает слона
символ «Q» обозначает королеву
символ «K» обозначает короля
Гарантируется, что есть один король.
Исходные данные
В случае мата в первой строке выведите Checkmate, а в следующих строках выведите клетки всех фигур, наносящих шах в произвольном порядке.
В случае пата в первой строчке выведите Stalemate.
В противном случае выведите «Continue» и в произвольном порядке все ячейки, в которые король может совершить ход.
Заметка
В первом примере король может атаковать пешку на g7 и перейти туда, потому что эта клетка не находится под атакой белой фигуры.
no title
Иллюстрация к первому примеру.
В другом примере король не находится под шахматом. У него есть три потенциально возможных хода: b8, b7 и a7. Ход на b8 невозможен, потому что это приведет к шахмате от пешки на a7. Ход на b7 невозможен, потому что это приведет к шахматному туру на h7. Ход на a7 невозможен, потому что это приведет к шахматному туру на h7. Таким образом, король не находится под шахом, но совершить ход не может, что означает пат.
no title
Иллюстрация к другому примеру.
В третьем примере король находится под шахматой, вызванной пешкой на c4 и королевой на e5. Кроме того, любой ход короля оставить его под шахом, создающим мат.
no title
Иллюстрация к третьему примеру.
Примеры
Ниже вы найдете примеры входящих данных и ответов, которые должна вывести программа.

Входные данные №1
......K.
…r.pp.
......b.
pp..n.r.
....p...
.......p
...p.b.p
..Q..n..
Ответ №1
Continue
g7
Входные данные №2
Kp......
p......r
........
.n......
........
........
p.pppppp
r.bQ.b..
Ответ №2
Stalemate
Входные данные №3
r.......
.p...p.n
bbp.rp.
...KQr.
..p...r.
.p......
..p.pp..
...n....
Ответ №3
Checkmate
c4
e5
Входные данные №4
........
......K.
.....ppp
........
........
........
........
..QQQQQQ
Ответ №4
Continue
f8
g8
h8

0