10401 - Injured Queen Problem

[hoang]

more detail please. I cant got it. This problem has taken me so much time. Please help !!!
Thanks .

[jurajz]

I think, that there is a mistake in input description. Input description says, that "Each line expresses a certain board status". But it seems, that there are blank lines. I have many WA's. When I add one line in my program (skipping blank lines), I have AC. So if anybody has WA, beware of blank lines and maybe it will be AC...

[stcheung]

Took me a while to understand what the previous hints meant when they mentioned memoization and creating a dp table. Let me try elaborating on that.

Assuming n is board size, let's start with the 2nd to last column. Let c denote this column. For each row r in column c, if you put a queen on (c, r) then how many different ways can you put a queen on column c+1? If the queen is preset in column c+1 at row p, then the answer is just dp[c+1][p]. Otherwise, you have to find the sum for dp[c+1][r2] for all r2 such that a queen placed on (c+1, r2) will not attack the queen you are trying to put on (c, r).

[Sedefcho]

I just want to confirm what jurajz mentioned above.
The input file seems to indeed contain some blank lines.
If you don't take this into account you will most probably get WA.
To get ACC just skip them (the blank lines).

So in C++ we may do something like that.
That would be enough (given the current judge input).

Code: Select all

while (gets(str))
{

   int len = strlen(str);

   if (len==0) continue;

   // process this input line (str)
   ......
   
}

Hope this remark may help someone.

[metaphysis]

Confirmed, the judge input contains line(s) which is blank. You can get AC by ignoring it.