I have a lazy version that I think works. Total up your current row and your current column. Go whatever direction is less. Repeat until you are at the goal.
Quzah.
I have a lazy version that I think works. Total up your current row and your current column. Go whatever direction is less. Repeat until you are at the goal.
Quzah.
Hope is the first step on the road to disappointment.
Nah, this wont work for wacky cases like the followingOriginally Posted by quzah
Your algo would head down instead of right, which will cost you more in the long run.Code:1 1 1 1 20 2 1 1 1 20 2 1 1 1 20 2 1 1 1 20 2 1 1 1 1
What's with all the bazaar solutions?!
Is this problem not screaming "Use the A* algorithm" loud enough?
You most definitely need to be comfortable with linked-lists and dynamic memory allocation, however you solve this.
By the way, have fun solving this one:
Code:1 1 1 1 1 99 14 12 8 2 1 89 2 2 2 4 1 79 2 8 1 1 1 69 2 4 15 17 21 59 2 2 2 2 2 1
Last edited by iMalc; 03-01-2011 at 12:35 AM.
My homepage
Advice: Take only as directed - If symptoms persist, please see your debugger
Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"
Mine solves that. Straight down the left side, straight across the bottom.
Quzah.
Hope is the first step on the road to disappointment.
It gets there, but still fails to find the fastest path. iMalc highlighted the fasted path in red text. Yours gets to array[2][0] with a cost of 1 + 14 + 2 = 17. iMalc's path gets there with a cost of 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 2 + 2 + 2 = 16. After that, you both follow the same path, meaning he beats you with a cost of 31 to your 32.
I did the math in my head.Too tired I guess.
Quzah.
Hope is the first step on the road to disappointment.
Yeah I made that particular maze to demonstrate that the optimal path doesn't necessarily involve only moving right or down, but also may involve moving left or upwards.
I also picked several of the constants such that it was only just more efficient to follow the hilighted path. I could have made the hilighted path all 1's and the other spaces all 99's, but that might fool some people into thinking that a "move towards the lowest number" algorithm (a.k.a Hill Climbing) would always work. Change the 14 to 11 and you'd certainly be best going straight down though.
My homepage
Advice: Take only as directed - If symptoms persist, please see your debugger
Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"
It also makes it look like the only solution though is to take whatever number is lowest from your immediate square. Which means this would get you stuck:I was getting hung up on trying to make it only check east and south of you, since he had mentioned working from 0,0 to N,N. For some reason I got it in my head to try to work a solution that only was checking two directions of travel.Code:1 1 5 2 3 5 1 5 5 1 5 5
Quzah.
Last edited by quzah; 03-01-2011 at 02:30 AM.
Hope is the first step on the road to disappointment.
The classical solution to this problem: Dijkstra's algorithm. A* would also work, but without a good heuristic, it wouldn't be much of an improvement.
Don't quote me on that... ...seriously
