|
|
Some good test cases: 2 8 3 01100011 00011000 1 2 0 00 Edited by author 07.02.2021 19:15 8 10 4 0000011000 0000110000 0000011000 0000110000 0000000000 0000000000 0000000000 0000000000 You should also try switching N and M (10 8) Edited by author 08.02.2021 16:48 10 10 5 0000000000 1000000000 1100000000 0111100000 0010110000 0000000000 0000000000 0000000000 0000000000 0000000000 AC finally!!! I used a randomized approach, but in the end, I needed to use a special seed. Nice problem, but unfortunately, I wasn't able to find test 74 to share here. Use the "SHAMANIZM" to overcome time-limit ;) Another advice: I guess that rested domino must form graph with next specific: It must be reduced to empty by sequental removing of vertex with degree=1 and adjacent with one. ("должен общипываться").What kind of these graphs? Edited by author 18.06.2008 14:10 Dominos are usually solved by finding perfect bipartie matching between odd and even cells (for their x+y). Now the problem is to fix minimal number of matched edges, so that maximum matching over remaining graph is unique. If there is alternating cycle, then matching is not unique. Edited by author 26.08.2008 07:12 What algo could we design based on it? 1. Find all cycles. 2. For each edge form set of all circles containig it. 3. Find minimal covering of set of all circles. Shortly, we should use minimal covering problem? Edited by author 12.02.2009 12:11 sure there is not more than min(n,m)/2+3 ones, but how we can prove or say its wrong there is no more optimal solution First,I think it might use "Bit DP" to solve this problem.But I failed Second,I think it might have a method to make a solution for given N,M .But I can't find this method. Last,I want to calculate all the case because N and M is very small.But I can't decide whether it is the best solution for each case. I have no idea for this problem.Could you please tell me how to solve this problem?Thank you. By the way,I'm sorry for my poor English.I wish you could know what I say. If there is at least one empty cell, every cell could be covered more than one way, and there is a way to cover all the cells, there is another way to cover all the cells? Your reasoning is wrong. I give you example. Could you find more than one way for cover this cells? 110000 011000 001100 000000 000000 000000 this case works, only by making "one-way" steps i can fill the board, 11GGEE 211FFD 2311CD 4388CB 46699B 5577AA note that "EVERY cell could be covered more than one way" in your case this wrong for cell (2,1) Edited by author 27.04.2008 02:03 |
|
|