Page 1 of 1
10937 - Blackbeard the Pirate
Posted: Sun Oct 16, 2005 8:29 am
by Cho
Can I assume there is exactly one landing point '@'?
I think this one is almost the same as 10818 (Dora Trip), but I got WA with the modified code from 10818.
Posted: Sun Oct 16, 2005 10:01 am
by sohel
Yes, there is only one landing point..
But this can vanish if the input is like this..
3 3
*@.
...
..!
The answer for this is -1.
Posted: Sun Oct 16, 2005 10:18 am
by Cho
Yes, I can handle it properly.
Posted: Sun Oct 16, 2005 12:08 pm
by Cho
I passed that too.
Probably stupid mistake. sigh...
[EDIT:] Just got the mistake, thx for the response.
Posted: Sun Oct 16, 2005 3:11 pm
by polone
would you say what mistake you've found?
I passed the two too but not accepted
Posted: Sun Oct 16, 2005 3:57 pm
by Cho
Originally, I use the following code to check whether (r, c) is safe from the angry natives:
Code: Select all
int dx[]={1,1,0,-1,-1,-1,0,1}, dy[]={0,-1,-1,-1,0,1,1,1};
for(i=0; i<8 && map[r+dy[i]][c+dx[i]]!='*'; i++);
Then, (r, c) is a safe location iff i==8. However, the above code forget to check whether 0<=r+dy
<h && 0<=c+dx<w.
Posted: Wed Oct 19, 2005 12:33 am
by TISARKER
~ Water. Blackbeard cannot travel over water while on the island.
I did not understand above line.
I did not understand the use of '~'
I did not understand when '~'point will be used.
Is there any tricky case?.
Please help.
Posted: Wed Oct 19, 2005 6:27 am
by Cho
'~' is somewhere you can't go to. I simply replace '~' with '#'.
i think there's something wrong in the test case...
Posted: Fri Oct 21, 2005 8:38 am
by chanson
for(i = 1; i <= h; i ++)
{
scanf("%s", &map[1]);
for(j = 1; j <= w; j ++)
{
if (map[j] == '@') st = pr(i, j);
else if (map[j] == '!')
{
trea[nt ++] = pr(i, j);
map[j] = nt;
}
//when i added following code,i got a tle...
//if (map[j] != '*' && map[j] != '.'
//&&map[j] != '~' && map[j] != '#'
//&&map[j] != '!' && map[j] != '@') while(1);
}
}
and after i considered every symbol not in the list as '#' i got acc...
Posted: Wed Oct 26, 2005 6:20 pm
by N|N0
Is this a travelling salesman problem?
Does any simpler solution exist?
Posted: Wed Oct 26, 2005 8:09 pm
by cypressx
It is a travelling salesman problem
Re: i think there's something wrong in the test case...
Posted: Fri Dec 16, 2005 7:23 am
by L I M O N
chanson wrote:
and after i considered every symbol not in the list as '#' i got acc...
thx chanson, finally i just get accepted after 10/12 submissions. I never considered abt dirty input.
Posted: Wed Jun 21, 2006 12:46 pm
by shanto86
how to solve it? it is NP so backtrack(DFS)? any huristic required? or BFS?
Posted: Thu Jun 22, 2006 11:38 am
by sohel
That's right !
You have to use backtracking to solve this problem..
however, you will need the assistance of bfs to construct the input matrix.
Natural prunning along the way should help decreasing the run time.
Re: 10937 - Blackbeard the Pirate
Posted: Mon Oct 22, 2012 11:48 pm
by shakil_buet
replace every unnecessary characters with '#' , then use BFS(n times) to find all pair shortest path.
Then use the TSP algorithm
check this input
3 3
..*
.@.
.!~
3 3
.!*
...
.@~
output :
-1
-1