Ok, ... it's easier to view it this way ... consider a maximum 4x4 board. So, this is the same as 16 cells. In each cell, obviously it could either be 0 or 1, ... 0 being empty, and 1 being occupied.
Just looking at the fact above, ... you can see we can have at most 2^16 combinations or states... which is pretty small 65536. Out of those 65536, find the "valid" states. That's your answer. On 2/20/07, ramtin <[EMAIL PROTECTED]> wrote: > > > > I'm sorry but I couldn't understand your code > > > and I think we can't use BackTrack because it is useful for problem > that we want to find a good leaf > but in this problem we must check all possible combinations > > > On Feb 20, 11:34 pm, "Lego Haryanto" <[EMAIL PROTECTED]> wrote: > > Won't brute force does the trick? Looks like it's at most 4x4 .... > (correct > > me if I'm wrong). You could play around with bitmasks probably, ... > treat > > each cell as one bit, ... probably also worthwhile to see what the > bitmask > > corresponds to the "controlled" cells if a rook is placed in certain > cell, > > ... > > > > Don't trust the following pseudocode completely because this is not > tested > > and I just wrote it on the fly, but I just want to show the idea .... > > > > function calcWays(state) > > if (state == ALL_FILLED) return 1; > > ways = 1; // this state itself is good > > for each unset bit in the state bitmask do > > nextState = state or (bitmask if this cell is occupied) > > ways += calcWays(nextState) > > endfor > > return ways > > end function > > > > On 2/20/07, ramtin <[EMAIL PROTECTED]> wrote: > > > > > > > > > Hi, > > > > > could anybody help me to solve this problem > > > > >http://acm.zju.edu.cn/show_problem.php?pid=1002 > > > > -- > > Fear of the LORD is the beginning of knowledge (Proverbs 1:7) > > > > > -- Fear of the LORD is the beginning of knowledge (Proverbs 1:7) --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
