10605 - Mines For Diamonds

[Destination Goa]

Hmm... Either test data is weak or there's indeed a polynom on number of diamonds and number of possible entrances.

[Adrian Kuegel]

I guess test data is weak (but I don't have the test data on my computer here, so I can't check). With how I understood the problem first, greedy strategies seemed likely to fail on random inputs. After I realised I understood the problem wrong, I didn't change the input.
I would be interested what your program would print in following case:

Code: Select all

10 10
##########
#........#
#........#
#........#
#...*....#
#........#
#...*.*..#
#...#....#
#...#....#
##########

Output should be 6.

[Adrian Kuegel]

I just checked with a few submissions, that the test data is indeed weak. I will try to generate better inputs.

[Destination Goa]

Adrian,

It outputs 6.

Check your private inbox in several minutes (writing my algo right now).

[Adrian Kuegel]

For all who get WA after rejudge and think their program is right:
The new data set contains one invalid test case where 24 grid squares are needed. Sorry for my mistake, I already mailed the new data set to Carlos, I hope it is fixed soon.

Edit: fixed

[rage_true]

I always get TLE on this problem.
Using brute forse on each step I try go from one diamante to another or go to exit(when i go to exit i find another unused diamonde and use recursion again).
How can i prune it?
Give me some hints.Plz.

[ziliang]

i just got ac.

i noticed that each diamond must connect to another diamond or the wall.

so i enumerate the father of a diamond node. and then calculate the total langth.


i got acc but i don't know how to prove my method right.


i wonder how you guys solved this problem,and whether my algo was right?

[mak(cse_DU)]

i just got ac.

i noticed that each diamond must connect to another diamond or the wall.

i wonder how you guys solved this problem,and whether my algo was right?

You are right "Ziliang".
I solved is using DP(TSP).
It will help some one:

Code: Select all

1
5 11
###########
#.........#
#..**.....#
#.........#
###########

Output:

Code: Select all

3