Shortest Path in a Maze

[MysticVegeta]

hi, I have been tring to code this problem in Dwite. It involves to find the shortest path in a maze from path A to B.

Quote:

5 5
#A###
#...#
###.#
#...#
#B###
10 8
########
#....#.#
###....#
A.#.##.#
#....#.#
###..#.#
#...##.B
#..##..#
##.....#
########

Any Idea?

[Delos]

I could think of some sort of graphical solution to it. One could plot a line that connects A to B via the pathways (some nifty recurssion would be used to ensure that in the end, only the direct path is saved) and if multiple paths are found, one would simply determine the length of each resultant line.
The details of this though, elude me. I know there are ways of doing it, having seen it been done before, but just how it is...

[zylum]

the easiet but slowest method would be recursion... you would try all possible paths until you find one. you store a value for the length of the path and a variable that holds the shortest length. if you find a path, check if its length is smaller than the current shortest path.

pseudo code:

code:

int findpath (int sx, int sy, int fx, int fy, d, boolean[][] map)   if (sx and sy is not a valid point) return maxIntValue   if (sx == fx and sy == fy) return d   map[sx][sy] = false   minValue = findpath (sx + 1, sy, fx, fy, d+1, map)   minValue = min(minValue, findpath (sx - 1, sy, fx, fy, d+1, map))   minValue = min(findpath (sx, sy + 1, fx, fy, d+1, map))   minValue = min(findpath (sx, sy - 1, fx, fy, d+1, map))   map[sx][sy] = true   return minValue + d end findpath

another way i suppose you can do it is find the distance between all vertecise and create and adjacency matrix and use floyd's algorithm on it.

or you could always impliment one of the standard pathfinding algorithms like the A* (which is pretty complex)

[MysticVegeta]

I was thinking that maybe i can do this ->

1> Assign every point in a 2d array.
2> run the 2 loops (2d array) and when it finds an "A",
3> "counterstart" = true, position of "A" (x, y) = 1
4> continue the loop untill it finds the next dot. When it does ->
5>

code:

if dot(x, y) shares a direction with the previously postion of (x, y) being 1  then count += 1 end if

6> Repeat till "B",
7> Do the same thing for other directions except this time make the locations (x, y) = 2.
8> So on and so forth.

Looks like its gunna take time, so i was just wondering if this will work, comments?

Btw, I didnt get to any complex algorithms, matrices, etc (will be finishing grade 9 in 2 days) but i plan to read some books for prior learning.

thanks,
Tan

[zylum]

well the first example that i posted was simple recursion... im not sure how this would be done with loops but either way im sure recursion would be a lot easier. if youre not familiar with recursion i suggest you learn it if you want to do contest type programming. plus its really interesting.

1> Assign every point in a 2d array.

this is what i mean when i use map in my pseudo code... map is a 2d array of boolean type. true means you can travel on that square and false means its a wall.

so the basic recursive method would be to start at the starting position and go in all posible directions. ie up/down/left/right. thats if the direction is permisable ie its not a wall or out of bounds. everytime you go to a new square you mark the old one as false so you dont travel on it again. to go to the next square you just call your function again but with updated perameters such as new starting position and updated map array and distance traveled. once you reach the finish, you check your distance vs your shortest distance variable and update its value if the new distance is shorter...

[MysticVegeta]

ic ic, i never thought about a boolean array lol.
Anyways, How can people code this in 45 mins??? or maybe i just underestimated grade 12's

[zylum]

its not hard once you do a couple of similar problems... there are much harder problems on the CCC... dwite is sort of a joke if you ask me.

if youre serious about this kind of thing check out www.topcoder.com/tc
they hold weekly online contests. the next 2 even have cash prizes! if you go on this site regularly untill your in grade 12 you should be able to be in the top 3 in canada in CCC.

[Martin]

This was a stupid dwite question.

The shortest path is easy to calculate, but the solution is not always efficient. Think of it like this: in actuality, would you like the shortest path, or a path that is probably the shortest (and if not, very close to being the shortest) and takes significantly less memory to calculate?

Google for the A-star algorithm. A much better solution.

[zylum]

ya i suggested A* but this is a dwite question... with the time constraints and his skill level i think a simple recursive solution would be best for him especially if the problem constraints are small (dwite rarely has tight constraints)

[MysticVegeta]

Zylum : I registered the Top Coder thingy. heh. It doesnt have Turing as your default language so i put C++, lol. I can solve some of them in C++ that i can solve in Turing.

Anyways, I will search for the A-star algorithm and maybe i will just use the 2d boolean array, code is in progress, lets see how many months it takes...

[zylum]

good job! the next contest is this wednesday, unfortunately i wont be able to participate this week.

[MysticVegeta]

you see i was in this practice arena and i was a doing a 250 question so in the code typing area i put somethinglike this ->

code:

#include <iostream> int main() { cout >> "eh?"; }

Why did that have problems compiling? Gave me the following errors:

Quote:

Your code did not compile:

errors compiling:

In file included from top level:3:
StringContents.cc: In function `int main()':
StringContents.cc:3: `cout' undeclared (first use this function)
StringContents.cc:3: (Each undeclared identifier is reported only once for each
function it appears in.)
In file included from top level:10:
Your class or method was improperly declared: In function
`std::vector<std::string, std::allocator<std::string> >
_wrapper::thunk(std::vector<std::string, std::allocator<std::string> >)':
Your class or method was improperly declared:20003: invalid use of undefined
type `struct StringContents'
end of your submission:10030: forward declaration of `struct StringContents'

[zylum]

code:

//#defines go here using namespace std; struct ClassName {     public:     returnType methodName (varType parameters) {                 //your code goes here                 return whatEver; // must be of type returnType ie int or double or <vector>     } };

your C code always has to have that structure. what they do to test your code is create an instance of your class and call the method in the class. therefore it is necessary to declare the class and method otherwise you will get errors.

[thegoose]

Martin wrote:

This was a stupid dwite question.

The shortest path is easy to calculate, but the solution is not always efficient. Think of it like this: in actuality, would you like the shortest path, or a path that is probably the shortest (and if not, very close to being the shortest) and takes significantly less memory to calculate?

Google for the A-star algorithm. A much better solution.

Actually in this case with a grid maze, the shortest path could be calculated in O(RC) time and O(RC) memory using BFS, where R is the number of rows and C is the number of columns. Since the reading the whole maze in takes is O(RC) time and the maze takes O(RC) storage, there is no point not doing the shortest path. (A* is also considerably harder to code compared to BFS from what I heard)

[MysticVegeta]

Sorry i know its been over a month, but i coded the problem using recursions but runs really really really slow. No way any processor would be able to debug it in 2.5 seconds, and what is this algorithm you are talking about?? Where can i find info on this? I would do a google on this but i dont know what to search for...