The backtracking method is also known as the test method, the method will give up the limitations of the size of the problem, and will give a one-piece and test in a certain order. When the current candidate is not possible, select the next one. Candidate; if the current candidate does not satisfy the problem requirements, meet all other requirements, continue to expand the scale of the current candidate, and continue to test. If the current candidate is satisfied, when all the requirements, including all the requirements, including the problem scale, The candidate is a solution of the problem. In the backtracking method, give up the current candidate, find the next candidate process is referred to as a backtrack. Expand the scale of the current candidate, and continue the test of the test.
In order to ensure that the program is able to terminate, adjust, it must be guaranteed that the filler sequence that has been abandoned is not tried again, that is, according to some ordered model to generate a fill sequence. The candidate given the candidate sets the sequence of inspected, A candidate is generated one by one in this order and test it.
For labyrinth problems, I want to use back tips forces to sort the solution to ensure that the missed fill sequence is not trial again. In the two-dimensional maze, start from the starting point, each point according to the four neighborhood For example, according to the right, upper, left, bottom search, there is a road, there is no way to return, and the front is searched in front of the next direction to constitute a ordered model. The following table is the labyrinth
{1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1, 1 0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }
Starting from the starting point, search for the next point of the selected point column constitutes the number column, if there is no way to search in four directions, return, and add 1, and put it in this class ... ...
1 2 3 4 5 6 7 8 9 10 1 2 3 3 3 2 ... Y 0 1 2 2 2 3 4 4 ... C 1 1 3 3 1 1 2 1 ...
#include
Linkstack Top [100]; // Maze Matrix INT MAZE [N1] [N2] = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 10, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 10, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,};
INT I, J, K, M = 0;
Main () {// Initialization TOP [], set all directions to left for (i = 0; i // Print the original labyrinth matrix for (i = 0; i
