迷宫问题-回溯法

2017-06-15

　　用二维数组maze[m][n]表示迷宫，数组中元素是0表示通道，元素是1表示墙，问题：求一条从入口到出口的无环路径。

　　回溯法求解：从入口出发，沿着某一个方向进行探索，若能走通，则继续向前走；否则沿原路返回，换一个方向再进行探索，直到找到一个出口，或者所有可能的探索都以失败告终。思路与DFS一致。

　　求解的程序中，设迷宫入口为maze[1][1]，出口处为maze[m-2][n-2]，入口、出口的值显然为0，任意时刻在迷宫的位置用maze[i][j]表示。从maze[i][j]出发，可以探索的方向有上下左右（北南西东）四个，根据maze[i][j]与相邻位置的关系，用一个数组direction[4][2]存储maze[i][j]的四个方向上i和j的增量值，通过该增量值表来修改maze[i][j]的位置，例如现在从maze[i][j]向东走一步，则下一位置的坐标就是maze[i+direction[0][0]][j+direction[0][1]]。为了避免走到已经探索过的位置（包括现在探索路径上的和曾经在路径上的位置），凡是探索过的位置都做上记号。一旦某一点maze[i][j]纳入当前路径，就将其赋值为2。用一个栈记录探索路径中当前位置以及在该位置上所选的方向，栈中每个元素有三项：当前位置的行列下标和direction数组的下标值，栈中的元素类型为typedef struct{int x,y,d;}DataType;。

　　从入口开始，对每个当前位置都从东方向开始试探，若不能通过，则顺时针依次试探南、西、北方向（d依次等于0,1,2,3）。当选定一个可通的方向，即找到下一个位置后，把当前所在的位置纳入到探索路径中，并记录当前所在位置及所选的方向，以便往下走不通时可以顺着原路一步步退回来，每退一步后接着试探在该点上尚未试探过的方向，从下一个位置继续开始探索，如此反复直至到达出口。

　　编码时栈直接用了STL中的stack：

构造：stack st;创建一个空栈　　

stackst1(st2);复制栈

　　五个常用操作函数：

st.top();返回栈顶数据　

st.push(element);在栈顶增加element元素　

st.pop();弹出栈顶元素　

st.empty();判断栈是否为空　

st.size();返回栈中元素个数。
不用STL的话，用数组模拟栈也是很容易的，用一个top变量记录栈顶。

// the definition of array direction 依次是东南西北方向
int direction[4][2]={{0,1},{1,0},{0,-1},{-1,0}};

// definition of element's data type in the stack
typdef struct {
	int x,y,d;
}DataType;

void mazePath(int* maze[],int *direction[],int x1,int y1,int x2,int y2,int M,int N){
/*search one path in the maze[M][N]
  maze[x1][y1] is the entrance of the maze while maze[x2][y2] is the exit of the maze 
  1<=x1<x2<=M-2
*/ 
	int i,j,k;  // maze[i][j]:current position k:current direction
	int g,h;  // maze[g][h]:next position
	stack<DataType> st;  // stack definition
	DataType element;
	maze[x1][y1] = 2; // add entrance into path
	element.x = x1; element.y=y1;element.d=-1;
	st.push(element); // push entrance into stack
	while(!st.empty()){ // while the stack isn't empty,keep searching
		// get the top element of stack and try every possible direction
		element = st.top();
		st.pop();
		i = element.x; j = element.y; k=element.d+1;
		while(k<=3){ // try all four direction
			g = i+direction[k][0];
			h = j+direction[k][1];
			if(g==x2&&h==y2&&maze[g][h]==0){ // if maze[g][h] is the exit
				// have found the path,print the reverse path
				printf("the reverse path is : \n");
				while(!st.empty){ // print all the elements in stack
					element = st.top();
					st.pop();
					printf("the node is %d %d ",element.x,elment.y);
				}
				return ; // after outputting the path,over the function
			}
			if(maze[g][h]==0){// maze[g][h] has never been passed by and 
			// it isn't the exit
				maze[g][h] = 2;// mark 
				// push current position maze[i][j] and direction into stack
				element.x = i; element.y = j;element.d=k;
				st.push(element);
				i=g;j=h;k=-1;/*update current position to next position in the path*/
			}
			++k;
		}
	}
	printf("The path has not been found.\n"); // hasn't found the path when the stack is empty
}