迷宫问题（BFS）——数据结构实习

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<queue>
#include<stack>
#include<algorithm>
#define maxn 100

using namespace std;
int n, sx, sy, ex, ey;	//sx, sy 是地点， ex, ey是终点
//algorithm ,广度优先搜索 
struct node {
	int x, y;
	int data;
	int fx, fy;
	bool vis;
}a[maxn][maxn];

int dir[4][2] = {-1, 0, 1, 0, 0, 1, 0, -1}; //此数组为控制上下左右方向的数组 

void bfs(int sx, int sy, int ex, int ey) { 
	queue<node> q;	//建立一个 q 队列 
	while(!q.empty()) q.pop();	//对队列进行初始化
	struct node temp = a[sx][sy];
	q.push(temp);
	
	while(!q.empty()) {
		struct node now = q.front();
		q.pop();
		
		int tx = now.x;
		int ty = now.y;
		now.vis = true;
			
		if(now.x == ex && now.y == ey)	//到了终点 
			break;
		
		for(int i=0;i<4;i++) {
			int next_x = tx + dir[i][0];
			int next_y = ty + dir[i][1];
			if(next_x < 0 || next_x > n || next_y <0 || next_y > n)
				continue;
			if(a[next_x][next_y].data != 1 && a[next_x][next_y].vis == false) {
				a[next_x][next_y].fx = tx;
				a[next_x][next_y].fy = ty;
				q.push(a[next_x][next_y]);
				a[next_x][next_y].vis = true;
			}
		}
	}
	
	stack<node> s;
	int backx = ex, backy = ey;
	int step = 0;
	while(backx != sx && backy != sy) {
		s.push(a[backx][backy]);
		backx = a[backx][backy].fx;
		backy = a[backx][backy].fy;
		step++;
	}
	s.push(a[sx][sy]);
	step++;
	cout<<"迷宫最短路径是:"<<endl; 
	while(!s.empty()) {
		struct node temp = s.top();
		s.pop();
		cout<<'<'<<temp.x<<','<<temp.y<<"> ,";
	}
	cout<<endl;
	cout<<"迷宫的总步数是: "<<step<<endl;
}

int main() {
	int tmp;
	int b[15][15];
	cout<<"请输入迷宫方阵的阶数"<<endl;	 
	cin>>n;
	cout<<"输入迷宫的具体数据"<<endl;
	freopen("a.txt", "r", stdin);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++) {
			cin>>tmp;
			a[i][j].x = i;
			a[i][j].y = j;
			a[i][j].data = tmp;
			a[i][j].vis = false;	//false 表示为被访问，所以可以走 
			if(tmp == 5) {
				sx = i;
				sy = j;
			}
			else if(tmp == 8) {
				ex = i;
				ey = j;
			}
		}
	fclose(stdin); 
	bfs(sx, sy, ex, ey);
	return 0;
}

测试数据为：

5作为起点，8作为终点；   

1 1 1 1 1 1 1 1 1 1
1 1 0 0 0 1 1 1 1 1
5 0 0 0 1 1 0 0 0 1
1 1 1 0 0 0 0 1 0 1
1 0 1 0 1 1 1 0 0 1
1 0 1 0 1 1 0 0 1 1
1 0 0 0 0 1 0 0 1 1
1 1 0 1 0 0 0 1 1 1
1 0 0 0 1 1 0 0 0 8

1 1 1 1 1 1 1 1 1 1