10937 - Blackbeard the Pirate

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

Moderator: Board moderators

Post Reply
User avatar
Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

10937 - Blackbeard the Pirate

Post by Cho » Sun Oct 16, 2005 8:29 am

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.

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel » Sun Oct 16, 2005 10:01 am

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.

User avatar
Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho » Sun Oct 16, 2005 10:18 am

Yes, I can handle it properly.
:-?

User avatar
Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho » Sun Oct 16, 2005 12:08 pm

I passed that too.
Probably stupid mistake. sigh...

[EDIT:] Just got the mistake, thx for the response. :)

polone
New poster
Posts: 43
Joined: Sun May 08, 2005 2:31 am
Location: Taiwan

Post by polone » Sun Oct 16, 2005 3:11 pm

would you say what mistake you've found?

I passed the two too but not accepted

User avatar
Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho » Sun Oct 16, 2005 3:57 pm

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.

TISARKER
Learning poster
Posts: 88
Joined: Tue Oct 12, 2004 6:45 pm
Location: Bangladesh
Contact:

Post by TISARKER » Wed Oct 19, 2005 12:33 am

~ 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.
Mr. Arithmetic logic Unit

User avatar
Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho » Wed Oct 19, 2005 6:27 am

'~' is somewhere you can't go to. I simply replace '~' with '#'.

chanson
New poster
Posts: 1
Joined: Fri Oct 21, 2005 8:29 am

i think there's something wrong in the test case...

Post by chanson » Fri Oct 21, 2005 8:38 am

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

User avatar
N|N0
New poster
Posts: 36
Joined: Tue Jan 25, 2005 10:33 pm
Location: Ljubljana, Slovenija
Contact:

Post by N|N0 » Wed Oct 26, 2005 6:20 pm

Is this a travelling salesman problem?
Does any simpler solution exist?

cypressx
New poster
Posts: 41
Joined: Sun Jul 04, 2004 12:16 pm

Post by cypressx » Wed Oct 26, 2005 8:09 pm

It is a travelling salesman problem :)

L I M O N
Learning poster
Posts: 58
Joined: Wed Dec 31, 2003 8:43 am
Location: Dhaka, Bangladesh
Contact:

Re: i think there's something wrong in the test case...

Post by L I M O N » Fri Dec 16, 2005 7:23 am

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.

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm

Post by shanto86 » Wed Jun 21, 2006 12:46 pm

how to solve it? it is NP so backtrack(DFS)? any huristic required? or BFS?
Self judging is the best judging!

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel » Thu Jun 22, 2006 11:38 am

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.

shakil_buet
New poster
Posts: 2
Joined: Sun May 06, 2012 7:41 pm

Re: 10937 - Blackbeard the Pirate

Post by shakil_buet » Mon Oct 22, 2012 11:48 pm

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

Post Reply

Return to “Volume 109 (10900-10999)”