C++广度优先算法.md

测试数据：

5 4
0 1 0 0
0 0 0 0
0 0 1 0
0 1 0 1
0 0 0 1
1 1 4 3

程序如下：

//Author:PanDaoxi
#include <iostream>
using namespace std;
//定义结构体 
struct node{
	int x,y,step;
};
//map=地图 book=标记走过的点
int map[51][51],book[51][51];
//给结构体开长度 
struct node que[2501];
//移动的方向
int nt[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
//m,n=地图大小 sx,sy=当前自己的位置
//p,q=目标位置 tx,ty=中间过程点的坐标 
int m,n,sx,sy,p,q,tx,ty;
//设置队首、队尾指针
int head=1,tail=1;
//标记是否有解
bool flag=false;
//广搜函数
void bfs(){
	//起点入队
	que[tail].x=sx;
	que[tail].y=sy;
	que[tail].step=0;
	tail++;
	//标记当前入队点
	book[sx][sy]=1;
	//循环：后序子节点入队 
	while(head<tail){
		//向四个方向搜索
		for(int i=0;i<4;i++){
			//获得子节点坐标
			tx=que[head].x+nt[i][0];
			ty=que[head].y+nt[i][1];
			//出界的情况跳过
			if(tx<1||tx>m||ty<1||ty>n) continue;
			//判断可以用的点
			if(map[tx][ty]==0&&book[tx][ty]==0){
				book[tx][ty]=1;
				//入队
				que[tail].x=tx;
				que[tail].y=ty;
				que[tail].step=que[head].step+1;
				tail++; 
			} 
			//是否找到目标
			if(tx==p&&ty==q){
				flag=true;
				break;
			} 
		} 
		//判断是否找到目标
		if(flag) break;
		//出队
		head++; 
	}
} 
int main(){
	//输入
	cin>>m>>n;
	//初始化地图
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++){
			cin>>map[i][j];
		}
	} 
	//输入自己和目标的坐标
	cin>>sx>>sy>>p>>q;
	//广搜
	bfs();
	//输出解
	cout<<que[tail-1].step; 
	return 0;
} 

---

//Author:PanDaoxi
#include <iostream>
using namespace std;
struct node{
	int x,y,step;
}; 
struct node que[10001];
int book[101][101];
int next[12][2]={{-2,-2},{-2,2},
				{2,-2},{2,2},
				{-2,-1},{-2,1},
				{-1,2},{1,2},
				{2,1},{2,-1},
				{1,-2},{-1,-2}
				};
int head=1,tail=1;
int p1,q1,p2,q2,tx,ty,flag1=0,flag2=0;
int s1,s2;
void bfs(){
	que[tail].x=1;
	que[tail].y=1;
	que[tail].step=0;
	tail++;
	book[1][1]=1;
	while(head<tail){
		for(int i=0;i<12;i++){
			tx=que[head].x+next[i][0];
			ty=que[head].y+next[i][1];
			if(tx<1||tx>100||ty<1||ty>100) continue;
			if(book[tx][ty]==0){
				book[tx][ty]=1;
				que[tail].x=tx;
				que[tail].y=ty;
				que[tail].step=que[head].step+1;
				tail++;
			}
			if(flag1==0&&tx==p1&&ty==q1){
				flag1=1;
				s1=que[tail-1].step;
			}
			if(flag2==0&&tx==p2&&ty==p2){
				flag2=1;
				s2=que[tail-1].step;
			}
		}
		if(flag1==1&&flag2==1) break;
		head++;
	}
}
int main(){
	cin>>p1>>q1>>p2>>q2;
	bfs();
	cout<<s1<<endl<<s2<<endl;
	return 0;
}

---

//Author:PanDaoxi
#include <iostream>
using namespace std;
struct node{
	int x,y,step;
};
int book[101][101];
struct node map[10001];
int next[8][2]={
	{-2,-1},{-2,1},
	{-1,2},{1,2},
	{2,1},{2,-1},
	{1,-2},{-1,-2}
};
int n,m,sx,sy,tx,ty;
int head=1,tail=1;
void bfs(){
	map[tail].x=sx;
	map[tail].y=sy;
	map[tail].step=0;
	tail++;
	book[map[head].x][map[head].y]=0;
	while(head<tail){
		for(int i=0;i<8;i++){
			tx=map[head].x+next[i][0];
			ty=map[head].y+next[i][1];
			if(tx<1||tx>n||ty<1||ty>m) continue;
			if(book[tx][ty]==-1){
				map[tail].x=tx;
				map[tail].y=ty;
				map[tail].step=map[head].step+1;
				book[tx][ty]=map[tail].step;
				tail++;
			}
		}
		head++;
	}
}
int main(){
	cin>>n>>m>>sx>>sy;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			book[i][j]=-1;
		}
	}
	bfs();
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cout<<book[i][j]<<" ";
		}
		cout<<endl;
	}
	return 0;
}