Можно решить задачу эмпирически. В начале найдем решения по-честному,когда пешка стоит на 1 горизонтали(т.е. игра почти завершена). Все состояния A[x,y,1] нам уже известны,а состояния A[x,y,i] i>1 неизвестны. Из очередного состояния (т.е. увеличив i и рассмотрев любые x,y-коорд. слона) будем выбирать макс. значение среди всех переходов. Если состояние,в которое мы попадаем неизвестно,то снова вызываем рекурсию,пока не попадем в известное(такое всегда будет,т.к. на каждом шаге пешка сдвигается хотя бы на 1,а состояния А[x,y,1] известны). Как только из данного состоя ния мы попадаем во все известные, то данное состояние становится известным.

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

It's problem has mathematical solution in O(1).
You must analyze several variants ( when y2=1,2,3,>=4 ) and find strategy for white.

?

Edited by author 10.05.2012 01:08

1.If bishop can eat pawn - he can Win.
2.Use matrix (rows  - digits, columns - letters). Left-top cell has coords (8,a), right-bottom has coords (1,h)
3. Pawn go down (to row "1" ).
3.If you use recursive functions :
1 - goPawn()
2 - goBishop()
Pay attention, that checking (bishop win,pawn win,draw) must be only in special places(goPawn() and/or goBishop() )

Good luck.

Edited by author 25.07.2009 21:04

Edited by author 25.07.2009 21:04

It's not clear if black player can continue movement or not after eating white bishop.

Please, give me several tests because I cannot find my mistake.

Please, give me several tests because I cannot find my mistake.

"with the usual chess rules"?
if (pawn on the 7th horisontal) then can pawn go on the 5th horisontal?

Edited by author 16.01.2007 15:44

........
........
    char a[3],b[3];
    scanf("%s%s",b,a);
    x0=*a-'a',y0=a[1]-'1';
    x1=*b-'a',y1=b[1]-'1';
    if(x0<0||x0>7||y0<0||y0>6||
        x1<0||x1>7||y1<0||y1>7)
            x0/=0;
........
........
This code receive Crash (integer division by zero).

Edited by author 01.01.2007 07:28

Such code gets CE:

bx:=ord(LowerCase(ch)[1])-96;

You should use explicit typecast like that:

bx:=ord(LowerCase(string(ch))[1])-96;

Edited by author 01.01.2007 17:41

In the task said that the bishop is white. And then said that "the bishop is initially positioned at any square different from the pawn’s square". But it is WHITE bishop. Something strange...