一本通之广度搜索合集

今天的目的是练习所有关于搜索的题目，我一定加油，新题到今天就结束吧
关于洛谷上的题，也是尽量的能找回来就找回来，一些水题我就不整理了
废话少说，开干吧
其实搜索对于我来说并不难，之前在日照也都训练过了，但是有些遗忘，所以还得重复学习一下

细胞，貌似听说过这个题
也就是求连通块吧，不就是油田吗？
貌似这个题连数据范围都没有
注意这里要单独开一个字符输入，因为数组都是连一块的
还有就是，我在这里开了一个二维数组来存队列，其实意思和queue是一样的只不过要开结构体，这样更方便

#include
#include
#include
#include
#include
using namespace std;
int n,m;
char c;
int a[105][105];
int dx[]={1,-1,0,0};
int dy[]={0,0,-1,1};//方位数组 
int ans;
void bfs(int x,int y)
{
	ans++;
	int head=0,tail=1;//初始化队列的头和尾
	int que[10000][2];//也可以用stl的就结构体队列实现
	a[x][y]=0; 
	que[1][0]=x,que[1][1]=y;//进入队列，从当前元素开始
	int xx,yy;
	while(head>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>c;
			a[i][j]=c-'0';//注意这里要单独开一个字符输入，因为数组都是连一块的
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(a[i][j])
				bfs(i,j);
		}
	}
	cout< 
1330 最少步数 
象棋的步数其实都差不多的套路，只不过这个题的方位数组需要开的大一点
 
#include
#include
#include
#include
#include
using namespace std;
int n,m; 
int dx[13]={0,-2,-2,-2,-2,-1,-1,1, 1,2,2, 2, 2}; 
int dy[13]={0, 2, 1,-1,-2, 2,-2,2,-2,2,1,-1,-2};//方位数组 
int x2,y2,x3,y3;
int book[101][101];
int que[10000][4];//队列，前两个存储坐标，第三个存储步数 
int main()
{
	cin>>x2>>y2;
	cin>>x3>>y3;
	memset(book,-1,sizeof(book));
	book[1][1]=1;
	que[1][1]=1;
	que[1][2]=1;
	que[1][3]=0;
	int head=1,tail=1;
	int xx,yy;
	while(head<=tail)
	{
		for(int i=1;i<=12;i++)
		{
			xx=que[head][1]+dx[i];
			yy=que[head][2]+dy[i];
			if(xx>0&&yy>0)//判断出界
			{
				if(book[xx][yy]==-1)//为访问并且不出界就更新 
				{
					book[xx][yy]=que[head][3]+1;
					tail++;
					que[tail][1]=xx;
					que[tail][2]=yy;
					que[tail][3]=book[xx][yy];//计算步数
					if(book[x2][y2]>0&&book[x3][y3]>0)
					{
						cout< 
卡了我好长时间
 
1251 仙岛求药 
好早就听说过这个题，听说zp老师之前做到晚上12点还没做出来…
 今天是我听说之后的一年后，正式直面他
 但是这个题貌似并不难啊
 然后这个题我先用广搜做一遍啊
 
#include
#include
#include
#include
using namespace std;
struct node{
    int h,z,step;
}cur,net;
queues;
char a;
int map[30][30];
bool vis[30][30];
int d[5]={1,0,-1,0,1};
int n,m;
int sx,sy,ex,ey;
void bfs()
{
    if(sx==ex&&sy==ey)
    {
        printf("0n");return ;
    }
    while(!s.empty())s.pop();
    cur.h=sx;
    cur.z=sy;
    cur.step=0;
    s.push(cur);
    vis[cur.h][cur.z]=1;
    while(!s.empty() )
    {
        cur=s.front() ;
        s.pop() ;
        for(int i=0;i<4;++i)
        {
            int xx=cur.h +d[i];
            int yy=cur.z +d[i+1];
            if(xx>0&&yy>0&&xx<=n&&yy<=m&&map[xx][yy]!=1&&!vis[xx][yy])
            {
                if(xx==ex&&yy==ey)
                {
                    printf("%dn",cur.step+1);
                    return ;
                }
                net.h=xx;
                net.z=yy;
                net.step=cur.step+1;
                vis[xx][yy]=1;
                s.push(net);
            }
        }
    }
    printf("-1n");
}
int main()
{
    scanf("%d%d",&n,&m);
    while(n!=0&&m!=0)
    {
        memset(vis,0,sizeof(vis));
        memset(map,0,sizeof(map));
        for(int i=1;i<=n;++i)
            for(int j=1;j<=m;++j)
            {
                cin>>a;
                if(a=='@'){sx=i;sy=j;}
                else if(a=='*'){ex=i;ey=j;}
                else if(a=='#'){map[i][j]=1;}
            }
        bfs();
        scanf("%d%d",&n,&m);
    }
    return 0;
}
 
1253 抓住那只牛 
之前在open上做过，所以这里就直接把代码拿过来了
 其实这种做法比较简单
 
#include
#include
#include
#include
#include
using namespace std;
int tme[100050];
queue q;
int n,m;
void inp(int i,int j){
	if(j>=0&&j<=100000&&tme[j]==-1)
	{
		tme[j]=tme[i]+1;//计算路径
		q.push(j);//进入队列
	}
}
int main(){
	memset(tme,-1,sizeof(tme));
	cin>>n>>m;
	tme[n]=0;
	q.push(n);
	while(!q.empty())
	{
		int x=q.front();
		q.pop();
		if(x==m)
		{
			cout< 
1255 迷宫问题 
还有三个题，广搜就结束了
 这个题貌似很简单
 
#include
#include
#include
#include
#include
#define N 26
using namespace std;
int n=5;
char a[N][N];
bool vis[N][N];
int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
struct node
{
    int x;
    int y;
}q[N*100],res[N][N];
void print(int x,int y)
{
    if(x==-1&&y==-1)
        return;
    print(res[x][y].x,res[x][y].y);//递归输出路径 
    printf("(%d, %d)n",x,y);//中文的逗号。。。 
}
void bfs(int sx,int sy,int ex,int ey)
{
    int head=1,tail=1;
    memset(vis,0,sizeof(vis));
 
    vis[sx][sy]=1;
    res[sx][sy].x=-1;
    res[sx][sy].y=-1;
    q[tail].x=sx;
    q[tail].y=sy;//存储队列 
    tail++;
 
    while(head=0&&nx=0&&ny 
1252 走迷宫 
我不得不说这几个题的标题都如此的草率
 其实这几个题都差不多性质，我也懒得做了
 
#include
#include
#include
#include
using namespace std;
const int N = 10010;
int r,c;
char map[N][N];
bool vis[N][N]={0};
int dir[4][2]={{-1,0},{1,0},{0,1},{0,-1}};
struct node
{
	int x;
	int y;
	int step;//记录步数 
}q[N];
void bfs(int sx,int sy,int ex,int ey)
{
	int head=1,tail=1;
	vis[sx][sy]=1;
	q[tail].x=sx;
	q[tail].y=sy;
	q[tail].step=1;//初始进队 
	tail++;
	while(head=0&&nx=0&&ny