Finding paths in a labyrinth

[billchow24]

For example, I have an input text file like a labyrinth
I use the array[x][y] to storge each charater in the labyrinth
When i start at the top left hand corner, i need to go out to the
exit at the bottom right hand.
There are two paths as indicated as red and green.

My problem is that how can i stored the corrdinations of the
two paths by using array?
I mean i need to output the corrdinations of the feasible paths
from the start to the point to the end.

Thanks everyone!!

XXXXXXX
TTTTTTTX
XXXTXXTX
XXXTTTTT

[DemonGal711]

I'm assuming there was an extra T that didn't make it in there. I had to do something similar to this, so if you want to find the code I posted on here, feel free to go look.

Anyway, are you traversing the maze yourself by telling it to go right, left, up, down or is your program suppose to tell you the correct path to take?

For outputting, I would simply keep track of the two variables x and y, and save them to a vector/array/stack/etc before moving on. Then, once you get to the end, just read out what you stored in the container.

[billchow24]

I'm assuming there was an extra T that didn't make it in there. I had to do something similar to this, so if you want to find the code I posted on here, feel free to go look.

Anyway, are you traversing the maze yourself by telling it to go right, left, up, down or is your program suppose to tell you the correct path to take?

For outputting, I would simply keep track of the two variables x and y, and save them to a vector/array/stack/etc before moving on. Then, once you get to the end, just read out what you stored in the container.

Yes, i am doing the maze problem.
I have find the paths and set the feasible paths with 'T'
However, i don't know to output coordination of the each path
as a path may split into 2 or more direction.
Thanks

[DemonGal711]

So, if I understand correctly, you're given the maze, but you need to determine where there are walls and where the floor is? Like, if this was your maze, (it's a 6x6 with a border around it): example
Then you would need to output:

TTXTXX
TXTTTT
TTTXTX
XXXTTT
TXXTXX
TTTTTT

[billchow24]

So, if I understand correctly, you're given the maze, but you need to determine where there are walls and where the floor is? Like, if this was your maze, (it's a 6x6 with a border around it): example
Then you would need to output:

TTXTXX
TXTTTT
TTTXTX
XXXTTT
TXXTXX
TTTTTT

Sorry, i have confused you.
Actually, i have a maze but i have already found the paths for
going out and mark the paths 'T'.
The others that lead to dead end are not marks.
So, i only need to output the coordinations of the paths with 'T' marked.
Besides, your example have only one paths out, there may be more ways out in my problem.
Thanks

[DemonGal711]

Yeah, I just picked a one path one so I make sure I understood.

Well, couldn't you just save the coordinates as you go? When you place down a 'T', save the coordinates (in a container or string or something) and then output them at the end.

One thing you could do is store them in an vector of strings, and when you hit a fork, just make a copy of the first string, push it into the vector, and send each string down their respective direction.

Another thing you could try is running a recursive program that walks through your maze, but when it hits a choice, breaks into pieces to travel down each piece. That was you would get each path. You'd have to be careful storing it though... haven't figured out a good way to handle that yet.

Or, if you don't mind wasting some time, just walk through the maze as many times as there is a choice +1 (for the initial walk through). For your example, there is only 1 choice, whether they go down or right. So, you'd have to walk through your code twice. If you can write this code once, just looping it would be simple. And if you keep a running count of how many forks there are in the maze, you could make sure it loops that many times +1.

Not sure if that really helps, but it might give you an idea how to handle it. I'd have to see some code if you want more code oriented response.

[billchow24]

Yeah, I just picked a one path one so I make sure I understood.

Well, couldn't you just save the coordinates as you go? When you place down a 'T', save the coordinates (in a container or string or something) and then output them at the end.

One thing you could do is store them in an vector of strings, and when you hit a fork, just make a copy of the first string, push it into the vector, and send each string down their respective direction.

Thanks for your advice!
But, first i don't adopt the vector method as i haven't learnt it yet.
If i use the methods that when i place 'T' and save the coordinations, i don't know how to store them in different containers for different paths.
Can you give me some suggestions?

[DemonGal711]

Well, my best suggestion would be a string to hold a path, cause when you hit a break, you just pull up a second string, set the two equal, use one to go down one choice and the other to take the other. Of course, creating a new string in mid program would be difficult. If you knew there were two paths, you could just create an array of strings with two elements and it would work, but you'd have to figure out how to determine the number of paths in the maze first before you could do that (assuming you don't want to just initialize a maze to a massive size).

The recursive version I suggested might be your best choice. Have it be something like:

if (at end) cout << path;
else // determine the next direction & # of choices 
       // loop incase there are multiple choices
       // call program, pass path and direction to take.

That's how I would handle it, but it's really depends how comfortable you are with recursion I guess.