471,850 Members | 1,064 Online
Bytes | Software Development & Data Engineering Community
Post +

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 471,850 software developers and data experts.

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 3732
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
NeoPa
reply views Thread by NeoPa | last post: by

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.