468,513 Members | 1,763 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 468,513 developers. It's quick & easy.

kindly help me to write program in c

The problem is like this:-


A maze is a rectangular area, with m rows and n columns, with an entrance and an exit. The interior of the maze contains obstacles. The entrance is at the upper-left corner, and exit is at the lower-right corner. A rat in a maze problem is to find a path from the entrance to exit of a maze. A path is basically a sequence of positions, none of which is blocked, and such that each (east,west south,north) neighbour of the preceding position. Write a program to find such path, if exits, otherwise output the message "No solution for this maze"
Sep 5 '06 #1
2 3619
D_C
293 100+
A recursive solution is the way to do it. Suppose you have a data structure maze, which contains the current (x,y) position of the rat, and also an mxn matrix with obstacles and the rat's "history" marked (which locations it has visited). Your algorithm should be something like:
Expand|Select|Wrap|Line Numbers
  1. if(rat is in the exit position)
  2. {
  3.   do what is necessary;
  4.   return;
  5. }
  6. if(rat has not been left) // go left
  7. {
  8.   move left;
  9.   solve maze;
  10.   move right; // undo going left
  11. }
  12. // similarly for go down, go right, and go up also
Sep 5 '06 #2
The problem is like this:-


A maze is a rectangular area, with m rows and n columns, with an entrance and an exit. The interior of the maze contains obstacles. The entrance is at the upper-left corner, and exit is at the lower-right corner. A rat in a maze problem is to find a path from the entrance to exit of a maze. A path is basically a sequence of positions, none of which is blocked, and such that each (east,west south,north) neighbour of the preceding position. Write a program to find such path, if exits, otherwise output the message "No solution for this maze"
CODE:
1.start at entrance.
2.at this point u may have 3 ways to move forward,select any one of that ,say(i,j)th cell.
3.mark it as visited.
4.simultaneously build a tree using the marked cells along with entrance &exit.
5.so at this point u may have again 3 ways ,choose any one
if this is an obstacle,mark as deadend &backtrace
else repeat steps 2,3,4,5until u reach exit.
Apr 12 '07 #3

Post your reply

Sign in to post your reply or Sign up for a free account.

Similar topics

2 posts views Thread by Naren | last post: by
18 posts views Thread by jacob navia | last post: by
5 posts views Thread by roopeman | last post: by
1 post views Thread by Chris | last post: by
11 posts views Thread by Siddhu | last post: by
1 post views Thread by Sachin Garg | last post: by
1 post views Thread by fmendoza | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.