数据结构实验三迷宫问题

#include <bits/stdc++.h>
using namespace std;
int m=0,n=0;//输入m行n列的矩阵
//初始化8个方向
int dir[8][2]= {{0,1},{0,-1},{1,0},{1,-1},{1,1},{1,-1},{-1,1},{-1,-1}};
int mp[505][505];//地图
int visit[505][505];//用来记录
struct node {
	int pre,next;//记录前一个点的坐标
	int num;
	int x,y;//自己的坐标
};
int ppath;
struct mmp {
	node * path = (struct node *)malloc(1000*sizeof(struct node));
	int front,tail;
};
void bfs() {
	mmp q;
	visit[1][1]=1;
	node tmp ;
	tmp.x=1;
	tmp.y=1;
	tmp.pre = -1;
	tmp.num=1;
	q.path[1]=tmp;
	q.front=1;
	q.tail=2;
	while(q.front<=q.tail) {
		node tp=q.path[q.front];
		q.front++;
		if(tp.x==m&&tp.y==n) {

			int nnm=tp.num;
			ppath = 1;
			node r=tp;
			while(tp.pre!=-1) {
				r=tp;
				tp=q.path[tp.pre];
				tp.next=r.num;

			}

			while(tp.next!=0) {
				printf("(%d,%d) ",tp.x,tp.y);
				tp=q.path[tp.next];
			}
			printf("(%d,%d) ",tp.x,tp.y);
			printf("(%d,%d)\n",m,n);
			break;
		}

		for(int i=0; i<8; i++) {
			int tx = tp.x+dir[i][0];
			int ty = tp.y+dir[i][1];

			if((!mp[tx][ty])&&(!visit[tx][ty])&&tx>=1&&tx<=m&&ty>=1&&ty<=n) {
				visit[tx][ty]=1;
				node tq;
				tq.x = tx;
				tq.y = ty;
				tq.pre = tp.num;
				tq.num=q.front;

				q.path[q.tail]=tq;
				q.tail++;
			}
		}
	}

}

int main() {
	while(scanf("%d %d",&m,&n)!=EOF) {
		//初始化
		//1为墙 0为可行路径
		memset(mp,0,sizeof(mp));
		memset(visit,0,sizeof(visit));

		for(int i=0; i<=n+1; i++)mp[0][i]=1;
		for(int i=0; i<=n+1; i++)mp[m+1][i]=1;

		for(int i=0; i<=m+1; i++)mp[i][0]=1;
		for(int i=0; i<=m+1; i++)mp[i][n+1]=1;

		srand(time(NULL));

		ppath = 0;//初始化no path

		for(int i=1; i<=m; i++)
			for(int j=1; j<=n; j++)
				mp[i][j]=rand()%2;

		mp[1][1]=0;
		mp[m][n]=0;

		for(int i=0; i<=m+1; i++)
			for(int j=0; j<=n+1; j++) {
				if(mp[i][j])
					printf("%%");
				else printf(" ");
				if(j==n+1)printf("\n");
			}
		bfs();
		if(!ppath)printf("No path!\n");
	}
	return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券