Page 2 of 2
Posted: Mon Feb 21, 2005 9:13 pm
by Destination Goa
Hmm... Either test data is weak or there's indeed a polynom on number of diamonds and number of possible entrances.
Posted: Tue Feb 22, 2005 4:37 am
by 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.
Posted: Tue Feb 22, 2005 5:45 am
by Adrian Kuegel
I just checked with a few submissions, that the test data is indeed weak. I will try to generate better inputs.
Posted: Tue Feb 22, 2005 12:58 pm
by Destination Goa
Adrian,
It outputs 6.
Check your private inbox in several minutes (writing my algo right now).
Posted: Wed Feb 23, 2005 7:27 pm
by 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
10605 TLE
Posted: Tue Jul 05, 2005 8:10 am
by 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.
10605
Posted: Fri Feb 09, 2007 2:22 pm
by 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?
Re: 10605
Posted: Tue Apr 20, 2010 4:44 pm
by mak(cse_DU)
ziliang wrote: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: