more detail please. I cant got it. This problem has taken me so much time. Please help !!!
Thanks .
10401  Injured Queen Problem
Moderator: Board moderators
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...
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).
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).
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).
Hope this remark may help someone.
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)
......
}

 Experienced poster
 Posts: 117
 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.
My solutions for UVa problems: https://github.com/metaphysis/Code.