递归法和回溯法Recursionandbacktracking.doc

递归法和回溯法(Recursion and backtracking)
Recursion and backtracking
Some people say, is actually a recursive backtracking, wo-dimensional array into the map is a maze a very complex process. And this kind of transformation, know the maze before actually no maze, it is not reasonable. In this regard, I can only say that this is in order to recursive and recursive, and then give yourself a green light.
But the maze is not only by the above methods to go, the premise is, as long as you can walk out of the maze, do not need to find the shortest route on a possible 一 indeed, just a maze of obstacles to progress, once went through, no one go second times. The following method is put forward by a game player, without recursion, also do not need to play games or stack back - with the harvest.
Another solution
Please note that I use a coarse line route in the maze in the maze, in fact, as long as the entrance along the side of the wall, you can go to the exit, the game player called "on the go" - if you don't put the maze of pathways as a line, but an area of the graphics, soon You' 11 see. why. The programming is also very simple.
The following program compiled in TC2, can be compiled in VC6 for mobile dynamic performance, the use of gotoxy (),
VC6 is not this function, and stack maze No. 219 characters are not displayed in the operating system using Chinese page 32 of the console program. If you want to achieve in the VC6 (gotoxy) function is used for API, a simple procedure is not necessary, so he wrote with TC2, suddenly change to C language and still not meet.
ftinclude <stdio. h>
Typedef struct hero (int x, y, face: HERO):
Void set hero (HERO* h, int x, int y, int face) (h->x=x: h->y=y: h->face=face;}
Void go (HERO* h) (if (h->face%2) h->x+=2-h->face: else h->y+=h->face-l:}
Void goleft (HERO* h) (if (h->face%2) h->y+=h->face-2: else h->x+=h->face~l:}
Void turnleft (HERO* h) (h->face= (h->face+3)%4:}
Void turnright (HERO* h) (h->face= (h->face+l)%4;}
Void prin