10937 - Blackbeard the Pirate

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

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]

Yes, I can handle it properly.

[Cho]

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

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

[polone]

would you say what mistake you've found?

I passed the two too but not accepted

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

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

[Cho]

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

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

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

[cypressx]

It is a travelling salesman problem

[L I M O N]

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]

how to solve it? it is NP so backtrack(DFS)? any huristic required? or BFS?

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

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