广度优先搜索BFS（广搜）复习（c++）

走出迷宫的最少步数 

题目

 代码

#include <bits/stdc++.h>
using namespace std;
struct xiao_che_shi
{
	int x,y,v;
	xiao_che_shi(){};
	xiao_che_shi(int a,int b,int c)
	{
		x = a;
		y = b;
		v = c;
	}
};
xiao_che_shi che_shi[1700];
int head,tail;
int n,m;
char a[50][50];
int b[50][50];
int che_shi_x[] = {1,0,-1,0};
int che_shi_y[] = {0,1,0,-1};
int main()
{
	
	cin>>n>>m;
	for(int i = 0;i<n;i++)
	{
		for(int j = 0;j<m;j++)
		{
			cin>>a[i][j];
		}
	}
	che_shi[++tail] = {0,0,1};
	b[0][0] = 1;
	while(head<tail)
	{
		head++;
		for(int i = 0;i<4;i++)
		{
			int ma_che_shi_x = che_shi[head].x+che_shi_x[i];
			int ma_che_shi_y = che_shi[head].y+che_shi_y[i];
			if(ma_che_shi_x>=0&&ma_che_shi_x<n&&ma_che_shi_y>=0&&ma_che_shi_y<m&&a[ma_che_shi_x][ma_che_shi_y]=='.'&&b[ma_che_shi_x][ma_che_shi_y]==0)
			{
				che_shi[++tail] = {ma_che_shi_x,ma_che_shi_y,che_shi[head].v+1};
				b[ma_che_shi_x][ma_che_shi_y] = 1;
				if(che_shi[tail].x==n-1&&che_shi[tail].y==m-1)
				{
					cout<<che_shi[tail].v;
					return 0;
				}
			}
		}
	}
	return 0;
}

走出迷宫的最少步数2

题目

代码

#include <bits/stdc++.h>
using namespace std;
struct xiao_che_shi
{
	int x,y,v;
	xiao_che_shi(){};
	xiao_che_shi(int a,int b,int c)
	{
		x = a;
		y = b;
		v = c;
	}
};
xiao_che_shi che_shi[1700];
int head,tail;
int n,m;
char a[50][50];
int b[50][50];
int xx1,yy1,xx,yy;
int che_shi_x[] = {1,0,-1,0};
int che_shi_y[] = {0,1,0,-1};
int main()
{
	
	cin>>n>>m;
	for(int i = 0;i<n;i++)
	{
		for(int j = 0;j<m;j++)
		{
			cin>>a[i][j];
			if(a[i][j]=='S') xx1 = i,yy1 = j;
			if(a[i][j]=='T') xx = i,yy = j;
		}
	}
	che_shi[++tail] = {xx1,yy1,0};
	b[xx1][yy1] = 1;
	while(head<tail)
	{
		head++;
		for(int i = 0;i<4;i++)
		{
			int ma_che_shi_x = che_shi[head].x+che_shi_x[i];
			int ma_che_shi_y = che_shi[head].y+che_shi_y[i];
			if(ma_che_shi_x>=0&&ma_che_shi_x<n&&ma_che_shi_y>=0&&ma_che_shi_y<m&&a[ma_che_shi_x][ma_che_shi_y]!='#'&&b[ma_che_shi_x][ma_che_shi_y]==0)
			{
				che_shi[++tail] = {ma_che_shi_x,ma_che_shi_y,che_shi[head].v+1};
				b[ma_che_shi_x][ma_che_shi_y] = 1;
				if(che_shi[tail].x==xx&&che_shi[tail].y==yy)
				{
					cout<<che_shi[tail].v;
					return 0;
				}
			}
		}
	}
	return 0;
}

骑士巡游

题目

代码

#include <bits/stdc++.h>
using namespace std;
struct xiao_che_shi
{
	int x,y,v;
	xiao_che_shi(){};
	xiao_che_shi(int a,int b,int c)
	{
		x = a;
		y = b;
		v = c;
	}
};
xiao_che_shi che_shi[1700];
int head,tail;
int n,m;
int b[50][50];
int xx1,yy1,xx,yy;
int che_shi_x[] = {2,2,1,1,-1,-1,-2,-2};
int che_shi_y[] = {1,-1,2,-2,-2,2,-1,1};
int main()
{
	
	cin>>n>>m>>xx1>>yy1>>xx>>yy;
	xx1--;
	yy1--;
	xx--;
	yy--;
	che_shi[++tail] = {xx1,yy1,0};
	b[xx1][yy1] = 1;
	while(head<tail)
	{
		head++;
		for(int i = 0;i<8;i++)
		{
			int ma_che_shi_x = che_shi[head].x+che_shi_x[i];
			int ma_che_shi_y = che_shi[head].y+che_shi_y[i];
			if(ma_che_shi_x>=0&&ma_che_shi_x<n&&ma_che_shi_y>=0&&ma_che_shi_y<m&&b[ma_che_shi_x][ma_che_shi_y]==0)
			{
				che_shi[++tail] = {ma_che_shi_x,ma_che_shi_y,che_shi[head].v+1};
				b[ma_che_shi_x][ma_che_shi_y] = 1;
				if(che_shi[tail].x==xx&&che_shi[tail].y==yy)
				{
					cout<<che_shi[tail].v;
					return 0;
				}
			}
		}
	}
	return 0;
}