[数据结构与算法]DFS BFS 模板

BFS

BFS (Breath First Search)广度优先搜索 模板

struct jgt
{
	int x; //横坐标
	int y; //纵坐标
	int step; //到这一点走的步数
}

int bfs()
{
	memset(vis,0,sizeof(vis)); //多组数据需要初始化数组
	queue<jgt> q;
	jgt start,now,next;
	start.x=sx; //sx为开始点的横坐标
	start.y=sy; //sy为开始点的纵坐标
	start.step=0; //开始步数为0
	q.push(start);
	
	while(!empty())
	{
		now=q.front();
		q.pop();
		if(a[now.x][now.y]=='目标字符') return now.step;
		for(int i=0;i<4;i++) //一般可以走的为四个方向，上下左右
		{
			next.x=now.x+fx[i];
			next.y=now.y+fy[i];
            if(next.x>=1 && next.x<=m && next.y>=1 && next.y<=n && !vis[next.x][next.y] && a[next.x][next.y]!='不能走的字符') //m为行数，n为列数，即满足在范围内，且没被标记过的，而且要是能走的字符
            {
                vis[next.x][next.y]=1; 
                next.step=now.step+1;
                q.push(next);
            }
		}
	}
	return -1; //一条路都不通的话，返回-1
}

例题：https://vjudge.ppsucxtt.cn/contest/451141#problem/F 　密码：HPUACM

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;

struct jgt
{
    int x;
    int y;
    int step;
};


int n,m,sx,sy;
int fx[4]={0,0,-1,1},fy[4]={1,-1,0,0};
char a[25][25];
bool vis[25][25];

int bfs()
{
    queue<jgt> q;
    memset(vis,0,sizeof(vis));
    jgt start,now,next;
    start.x=sx;
    start.y=sy;
    start.step=0;
    q.push(start);
    
    vis[sx][sy]=1;
    while(!q.empty())
    {
        now=q.front();
        q.pop();
        if(a[now.x][now.y]=='*') return now.step;
        for(int i=0;i<4;i++)
        {
            next.x=now.x+fx[i];
            next.y=now.y+fy[i];
            if(next.x>=1 && next.x<=m && next.y>=1 && next.y<=n && !vis[next.x][next.y] && a[next.x][next.y]!='#')
            {
                vis[next.x][next.y]=1;
                next.step=now.step+1;
                q.push(next);
            }
        }
    }
    return -1;
}

int main()
{
	cin>>m>>n;
	for(int i=1;i<=m;i++)
	{
		for(int j=1;j<=n;j++)
		{
			cin>>a[i][j];
			if(a[i][j]=='@') sx=i,sy=j;
		}
	}
	cout<<bfs();
	
	
	return 0;
}

DFS

DFS (Depth First Search)广度优先搜索 模板

//求从一个点到另一个点走的最少步数

void dfs(int x,int y,int step)
{
	if(a[x][y]=='*') //等于目标符号
	{
		flag=1;
		minn=min(step,minn); //每次满足条件的时候取步数的最小值
		return;
	} 
	
	vis[x][y]=1; //标记
	for(int i=0;i<4;i++)
	{
		nx=x+fx[i];
		ny=y+fy[i];
		if(nx>=1 && nx<=m && ny>=1 && ny<=n && !vis[nx][ny] && a[nx][ny]!='#') dfs(nx,ny,step+1);
	}
	vis[x][y]=0; //回溯
}

例题：https://vjudge.ppsucxtt.cn/contest/451141#problem/F 　密码：HPUACM
！！！ 这个代码会超时 ！！！ 仅仅是一种思路

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;


int nx,ny,n,m,flag,sx,sy,ex,ey,step;
int minn=1<<30;
int fx[4]={0,0,-1,1},fy[4]={1,-1,0,0};
char a[25][25];
bool vis[25][25];

void dfs(int x,int y,int step)
{
	if(a[x][y]=='*')
	{
		flag=1;
		minn=min(step,minn);
		return;
	} 
	
	vis[x][y]=1; 
	for(int i=0;i<4;i++)
	{
		nx=x+fx[i];
		ny=y+fy[i];
		if(nx>=1 && nx<=m && ny>=1 && ny<=n && !vis[nx][ny] && a[nx][ny]!='#') dfs(nx,ny,step+1);
	}
	vis[x][y]=0;
}

int main()
{
	cin>>m>>n;
	for(int i=1;i<=m;i++)
	{
		for(int j=1;j<=n;j++)
		{
			cin>>a[i][j];
			if(a[i][j]=='@') sx=i,sy=j;
		}
	}
	dfs(sx,sy,0);
	if(flag) printf("%d\n",minn);
	else printf("-1\n");
	
	
	return 0;
}