ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1398. Bishop and Pawn

Solution 2( Idea)
Posted by Felix_Mate 22 Jun 2015 13:44
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