This problem can solve DP.
DP[x,y,i] где x,y-координаты слона and i- ордината пешки.
DP[x,y,1] найти легко( либо сразу съели и выигр.,либо проиграли).
Ответ: DP[x1,y1,y2].

Учитываем,в какой вертикали находится пешка(первая вертикаль-нижняя строка).
Рассмотрим очередное состояние(т.е. момент,когда i>1 и все состояния [х,y,j] j<i известны).
Во-первых, возможно,что состояние тривиально(т.е. мы съедаем пешку). Тогда DP[x,y,i]:=1;
Во-вторых, возможно,состояние непонятно. Тогда сделаем все возможные ходы слоном, пешка соответственно сдвигается на 1 или 2 позиции(в зависимости от горизонтали) и мы попадаем в предыдущую позицию(т.е. уже известную). Среди таких переход выбираем переход с макс. итогом( особый случай это горизонталь 2,где пешка может сходить на 2 клетки, но суть та же).Так же не следует забывать,что мы можем перегородить дорогу пешки. В этом случае нам(слону) ничья как минимум обеспечена.

Сложность O(n^4) (n*n- размеры поля; параметр i<=n, все переходы - это <=2*n позиций(не считая случая с 2 горизонталью,но это реально не влияет), позиций слона
n*n).

Edited by author 22.06.2015 13:50

Edited by author 22.06.2015 13:51

Edited by author 22.06.2015 13:55