PKU——3984迷宫问题

定义一个二维数组：

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表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。
‘’

//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <stdio.h>
#include <string>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <list>
#include <sstream>
#include <algorithm>
#include <cstring>
#include <iomanip>
#include <cmath>
using namespace std;

const int maxn = 100 + 10;
int n,m;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
int mg[5][5];
bool vis[5][5];

struct node
{
	int x,y;
	int step;
}A;
struct Par
{
	int x,y;
};
Par par[5][5];
void init()
{
	memset(par,-1,sizeof(par));
	memset(vis,0,sizeof(vis));
	A.x = 0;A.y = 0;
	A.step = 0;
	vis[0][0] = 1;
	par[0][0].x = 0;par[0][0].y = 0;
}
void bfs()
{
	queue<node> q;
	q.push(A);
	while(!q.empty())
	{
		node tmp = q.front();q.pop();
//		if(tmp.x == 4 && tmp.y == 4)
//		{
//			cout<<tmp.step<<endl;//打印步数的步骤
//			return;
//		}
		for(int i=0;i<4;i++)
		{
			int xx = tmp.x + dx[i];
			int yy = tmp.y + dy[i];
			if(mg[xx][yy]==1||xx<0||yy<0||xx>=5||yy>=5||vis[xx][yy])
				continue;
			node tp;
			tp.x = xx;tp.y = yy;
			tp.step = tmp.step + 1; 
			q.push(tp);
			vis[xx][yy] = 1;
			par[xx][yy].x = tmp.x;
			par[xx][yy].y = tmp.y;
		}
	}
}
void dfs(int x,int y)
{
	if(!x && !y) return;
	dfs(par[x][y].x,par[x][y].y);
	cout<<"("<<par[x][y].x<<", "<<par[x][y].y<<")"<<endl;
}


int main() 
{
	for(int i=0;i<5;i++)
		for(int j=0;j<5;j++)
		cin>>mg[i][j];
	init();
	bfs();
	dfs(4,4);
	cout<<"(4, 4)\n"; 
	return 0;
}