## 10937 - Blackbeard the Pirate

Moderator: Board moderators

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

### 10937 - Blackbeard the Pirate

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
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
Yes, I can handle it properly.

Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong
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
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
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
Contact:
~ 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?.
Mr. Arithmetic logic Unit

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

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:
Is this a travelling salesman problem?
Does any simpler solution exist?

cypressx
New poster
Posts: 41
Joined: Sun Jul 04, 2004 12:16 pm
It is a travelling salesman problem

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

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

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

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