471,850 Members | 1,064 Online

# 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