BFS poj 3948 简单bfs，注意打印路径的方法

#include <bits/stdc++.h>
using namespace std;
const int maxn=10;
const int dir[4] [2]={1,0,0,1,-1,0,0,-1};

struct p{
	int a,b;
	p(int A,int B):a(A),b(B){}
	p(){}
};


int maze[maxn][maxn];
queue<p> Q;

p pre[maxn][maxn];//巧妙的一点，可以用这种方法扩展到多维的路径的存储。
//dfs可以用一个vector来存储，bfs没有办法用那种方法（这句话写给我自己看哈~）
void bfs(){
	while(!Q.empty()) Q.pop();
		
	p s(1,1);
	maze[1][1]=1;
	Q.push(s);
	
	while(!Q.empty()){
		p tp=Q.front();
		Q.pop();
		if(tp.a==5&&tp.b==5) return;
		
		for(int i=0;i<4;i++){
			int xx=tp.a+dir[i][0];
			int yy=tp.b+dir[i][1];
			
			if(xx>=1&&xx<=5&&yy>=1&&yy<=5&&maze[xx][yy]!=1){
				p t(xx,yy);
				Q.push(t);
				maze[xx][yy]=1;
				pre[xx][yy]=tp;
			}
		}
	}
}
void showpath(p a){
	if(a.a==1&&a.b==1) cout<<'('<<(a.a-1)<<", "<<(a.b-1)<<')'<<endl;
	else {
		showpath(pre[a.a][a.b]);
		cout<<'('<<(a.a-1)<<", "<<(a.b-1)<<')'<<endl;
	}
	
}
int main() {
	for(int i=1;i<=5;i++)
		for(int j=1;j<=5;j++)
			cin>>maze[i][j];
	
	bfs();
	p a(5,5);
	showpath(a);
}