10401 - Injured Queen Problem

All about problems in Volume 104. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

Post by hoang » Mon Jan 30, 2006 2:44 pm

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

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

Re: 10401 - Injured Queen Problem

Post by jurajz » Sat Jun 07, 2008 1:35 am

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...

Experienced poster
Posts: 114
Joined: Mon Nov 18, 2002 6:48 am

Re: 10401 - Injured Queen Problem

Post by stcheung » Fri Jan 09, 2009 7:29 am

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).

User avatar
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Re: 10401 - Injured Queen Problem

Post by Sedefcho » Fri Feb 27, 2009 2:05 pm

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.

Experienced poster
Posts: 117
Joined: Wed May 18, 2011 3:04 pm

Re: 10401 - Injured Queen Problem

Post by metaphysis » Sat Feb 24, 2018 5:52 am

Confirmed, the judge input contains line(s) which is blank. You can get AC by ignoring it.
My solutions for UVa problems: https://github.com/metaphysis/Code.

Post Reply

Return to “Volume 104 (10400-10499)”