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
Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

10937 - Blackbeard the Pirate

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

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

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

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

Post by Cho »

Yes, I can handle it properly.
:-?

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

Post by Cho »

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 »

would you say what mistake you've found?

I passed the two too but not accepted

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

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

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

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

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

Post by Cho »

'~' 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 »

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

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

Post by N|N0 »

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 »

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 »

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 »

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

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

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

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

Re: 10937 - Blackbeard the Pirate

Post 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

Post Reply

Return to “Volume 109 (10900-10999)”