迷宫问题

定义一个二维数组： 

int maze[5][5] = {

	0, 1, 0, 0, 0,

	0, 1, 0, 1, 0,

	0, 0, 0, 0, 0,

	0, 1, 1, 1, 0,

	0, 0, 0, 1, 0,

};

它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。

Input

一个5 × 5的二维数组，表示一个迷宫。数据保证有唯一解。

Output

左上角到右下角的最短路径，格式如样例所示。

Sample Input

0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0

Sample Output

(0, 0)
(1, 0)
(2, 0)
(2, 1)
(2, 2)
(2, 3)
(2, 4)
(3, 4)
(4, 4)

解题思路：结构体保存结点的坐标，用全局的结构体数组保存路径。
DFS{
  如果到终点，返回。
  判断条件是否符合（是否是’1‘，是否是旧点）。
  搜索结点周围的每一个点。{考虑越界，设置为旧点，保存路径，然后递归下一个点）
}

#include <iostream>
using namespace std;
struct node{
	int x;
	int y;
};
int map1[5][5];
bool vis[5][5];
node path[50];
int flag = 0;
int dir[4][2] = {{1,0},{0,1},{-1,0},{0,-1}};
void DFS(node v, int step){
	if(flag) return;
	if(v.x == 4 && v.y == 4){
		flag = step;
		return;
	}
	if(vis[v.x][v.y] || map1[v.x][v.y]) return;
	for(int i = 0; i < 4; i++){
		int dx = v.x + dir[i][0];
		int dy = v.y + dir[i][1];
		if(dx < 0 || dy < 0 || dx >4 || dy > 4) continue;
		if(vis[dx][dy]) continue;
		vis[v.x][v.y] = 1;
		v.x = dx; v.y = dy;
		path[step].x = v.x; path[step].y = v.y;
		DFS(v,step+1);
		if(flag) return;
	}
	return;
}
int main(){
	node v;
	v.x = v.y = 0;
	path[0].x = path[0].y = 0;
	
	for(int i = 0; i < 5; i++)
		for(int j = 0; j < 5; j++){
			cin>>map1[i][j];
			vis[i][j] = 0;
		}
	DFS(v,1);
	for(int i = 0;i < flag; i++)
		cout<<"("<<path[i].x<<", "<<path[i].y<<")"<<endl;	
	return 0;
}