Можно решить задачу эмпирически. В начале найдем решения по-честному,когда пешка стоит на 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 c2 b2 WHITE a2 b2 DRAW a1 f7 WHITE d2 f7 WHITE g6 e2 BLACK h2 g2 DRAW h8 g7 WHITE 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 kill yourself by hitting the wall. =) it's very simple problem, to my mind. It's not clear if black player can continue movement or not after eating white bishop. Bishop moves first, so if at first pawn can capture bishop it does not matter. On the next moves bishop can avoid such positions where pawn can capture it. Please, give me several tests because I cannot find my mistake. And explain why I have WA#2. Edited by author 15.03.2008 20:17 You have a mistake in "Draw". Change in 6 line a='h' to a='g' and c='g' to c='h'. And in 9 vice versa. I'm a stupid man... Thanks! 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 Algebraic chess notation(srandart chess notation): ...First, the files (that is, lines running parallel to the direction the players are facing) are labelled with LOWERCASE letters a through h... Test#10 has uppercase letters. To admins: please fix bug. It seems you are right, I have AC. Many thanks! I think Test#20 has uppercase letters, too! The problem statement is unclear. It is not said that the letters might be capital. And the sample does not show it either. So the statement will be 99% misunderstood. That is why the authors should avoid such fuzzy expressions as "standard chess notation". Surely, the problem statement (or the tests) should be fixed. Now tests contain only LOWERCASE latin letters. Problem has been rejudged, 4 authors got AC. Edited by author 04.01.2007 01:29 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 Download FreePascal 2.0.4 and have no problem... I did so!!! 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... But it is WHITE bishop. And what? White bishop can be situated on black field too. Sorry! I understood my mistake... Program that getfor test b1 a3 answer WHITE receives AC. I think this test should be added because there are only 4 draw cases. |
|