Discussion of Problem 1122. GameOn test bwwb bbwb bwwb bwww My program gives 3, but right ans is 4 this test from 1060 Try iterative instead of recursive. moves wont exceed 16. Edited by author 25.08.2021 23:18 Edited by author 25.08.2021 23:19 My solution is very ugly Maybe yours is beautiful How nice is your solution? How ugly can it be? Just need to use three functions: convert board to 2-byte value, unconvert, modify board by making a move at (x, y). And with those, we just do usual BFS, until 0 or 65535 is reached. Unless of course you're not doing brute force but some smart solution. What? Why? You can't be serious. I'll try to scribble the concept in pascal... type TBoard = array[0..3, 0..3] of shortint; //the board TMod = array[0..2, 0..2] of shortint; //the modifier var md: TMod; ... procedure ModifyBoard(x, y: shortint; var board: TBoard); //x, y are coordinates of our move's center //board links to the board array we're modifying var i, j: shortint; begin for i:=-1 to +1 do for j:=-1 to +1 do if (x + i >= 0) and (x + i <= 3) and (y + j >= 0) and (y + j <= 3) then begin //out of bounds check if md[i + 1, j + 1] > 0 then board[x + i, y + j]:=1 - board[x + i, y + j]; //flipping if spot is marked for that end; end; I guess not more effecient than your bit operations, but definitely easier to read. You can, like, just convert 2-byte state into a full board and convert it back with separate functions if needed. Why? Because I have solved a very similar task Flip game I don't like to solve the same task with the same method twice I see, you weren't serious. Sorry. WBBB BBBW WBWB BBBB 101 010 101 2 BBBB BBWW BBBB WWBW 010 111 010 3 can you explain your examples I feel wonderful.:) Hi Clever Can you tell me your Email Address??? I've written a mail to you, but the chinese e-mail server is all borken...(there is some virus..) So I can't send the mail to you :( My mail address:vhappy@netease.com mine is 0.015 or better IT's not difficult to do it in 0.015s.=) Can you just say what's the idia of these fast solutions :? I want to know too...how does it do it so fast? wow, can you mail me my id is shlakshmanan@inautix.co.in There exists O(256*16*9) solution with 65536 byte dp[] memory..... a little hint: separate flipping cells in the 1- and 2- rows with flipping cells in the 3 - and 4- rows . Edited by author 09.01.2017 12:52 1. "За один ход можно перевернуть одну фишку и все соседние по горизонтали или вертикали с ней." Instead of "или" should be used "и". ("vertically and horizontally") 2. "Предписания комбинации на переворачивание фишек, попадающих за пределы поля, игнорируются." Hard to understand. Most clear will be: "Если ход попадает в клетку на границе поля, переворачиваются только те фишки, которые находятся в его пределах". Первое - с точки зрения русского языка, в текущем варианте условия все верно. Как клетка может быть соседней одновременно по горизонтали И вертикали??? Второе - имхо, как раз в текущем варианте условия все более понятно. В вашем варианте нужно еще думать - что такое "ход попадает в клетку на границе". Вообще, не вижу смысла придираться к текстам задач уже прошедших соревнований, если текст задачи не вызывает неверное толкование. Тем более с такими спорными замечаниями. "Или" в данном условии можно трактовать как "перевернуть все соседние по горизонтали или перевернуть все соседние по вертикали", то есть можно перевернуть не все, а только по одному из направлений. Это первое место в условии, которое сбивает с толку. Второе добивает. Что конкретно нужно игнорировать: всю комбинацию, или только только те фишки из нее, которые не находятся на доске (то есть, не существуют – как их вообще можно не проигнорировать)? Вот вам неверное толкование. Я не придираюсь к условию, а стараюсь сделать сайт чуточку лучше. Чтобы понять условие, мне пришлось вытащить английскую версию страницы из кэша Google в другом браузере. Edited by author 11.06.2014 22:58 По поводу первого - фраза "ВСЕ соседние [по горизонтали или вертикали] с ней" достаточно однозначно указывает, что переворачиваются ВСЕ клетки, соседние с данной, причем соседство может быть по горизонтали ИЛИ вертикали. На всякий случай для тех, у кого трудности с интерпретацией русского - внизу приведена картинка хода. Ну и на самый последний конец: данная фраза вообще не очень-то и важна для понимания условия, потому что потом описывается другая (расширенная) задача. Оффтоп: если погуглить, фраза "по горизонтали или вертикали" встречается примерно в 10 раз чаще, чем аналог с "и". Так что, если вы решили реформировать русский язык - то почему именно с этой задачи? Второе: "Предписания комбинации на переворачивание фишек, попадающих за пределы поля, игнорируются". Здесь опять русский язык, почувствуйте разницу: не "Комбинация, содержащая фишки, попадающие за пределы поля, игнорируется", а "Предписания комбинации на переворачивание фишек, попадающих за пределы поля, игнорируются". То есть когда реализуемая комбинация предписывает перевернуть фишку за пределами поля - это предписание игнорируются. Чувствуете разницу? То-то нынче снизили минимальный проходной балл на ЕГЭ по русскому языку - народ вообще перестал чувствовать и любить язык, на котором писали Толстой и Достоевский. Умничайте сколько хотите, мне ваши до ваших выпадов дела нет. Если администрация считает, что условие предельно однозначное, то так тому и быть. I don't now why!! AAAAAAAA!!!! WWWW WBBW WBWW WWWW 000 011 010 is it impossible?? WWWW WBBW WBWW WWWW 000 011 010 Why impossible? Answer has to be one, since choosing 2,2 cell will turn all cells to white. But I still get WA10. Please help . . . You've forgotten, that cenrtral piece must leave. Are you saying that we should not turn the piece at the center of mask? There was no task condition about that. who can help me???? BWBB WBWB WWBB BWWB 000 010 000 right answer is 7 my mistake was in using final mask=2^16, but it's wrong. Right mask is 0 and 2^16-1 I think that in test 1 to 6 'matrix of move' is symmetric. I get AC after my test: BBBB BBWB BWBB BWWB 001 010 011 It's obviously that correct answer is 1. We must make move in cell which is in '()'. B B BB B B WB B(W)BB B W WB and get BBBB BBBB BBBB BBBB Edited by author 05.02.2012 23:59 WWWW WWWW WWWW WWWW 010 000 010 If you have WA7, then check how you build and destroy your masks, they must be built in one order. I don't need more. I found my BIG bug. what's your big bug?I also got WA6. you can choose every square as a center and not only top-left 4 as i misunderstood. Edited by author 23.03.2011 18:45 I cant understand the problem statement. please explain it to me. sorry for my poor english!!! This problem very similar to problem #1060 from this site. The only difference bewtween them - at the 1060 we must flip 4 neighbors(up,down,left,right), here we must flip only those neighbors, who described with flip-mask(3x3 matrix). BTW, if flip-mask wiil be 010 111 010, solution will be completely the same with solution of 1060! ;-) Edited by author 04.11.2008 18:14 I think my solutioin is right but :( just produce all 2^16 possible play! if you get WA#1 you have forgotten to print "Impossible"! The 'Sapmle' should be 'Sample'... I won't post my sors because I use compression and it's very long. Does anyone know why it is giving me WA11 ? Is there and trick ? I'm going to die... |
|