## 10401 - Injured Queen Problem

Moderator: Board moderators

hoang
New poster
Posts: 4
Joined: Sat Jan 14, 2006 6:02 pm
Thanks .

jurajz
Learning poster
Posts: 69
Joined: Sat Sep 02, 2006 7:30 pm
Location: Slovakia

### Re: 10401 - Injured Queen Problem

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
Experienced poster
Posts: 114
Joined: Mon Nov 18, 2002 6:48 am
Contact:

### Re: 10401 - Injured Queen Problem

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
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

### Re: 10401 - Injured Queen Problem

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
Experienced poster
Posts: 139
Joined: Wed May 18, 2011 3:04 pm

### Re: 10401 - Injured Queen Problem

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