BFS学习笔记

LGZ-xczm|星君

2026-08-21 11:04:20

发布于：浙江

29阅读

0回复

0点赞

迷宫图

建图 
char g[N][N];
方向数组
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
标记数组
bool vis[N][N];
距离数组
int d[N][N];
// stl容器之一 ---- 数对 
pair<int,int> p;
// 模板 
void bfs(int bgx,int bgy){
	queue<pair<int,int>>q;
	// 初始化起点 
	vis[bgx][bgy]=true;
	d[bgx][bgy]=0;
	q.push({bgx,bgy});
	
	while(!q.empty()){
		// 取出队头 
		pair<int,int> t=q.front();
		q.pop();
		int x=t.first;
		int y=t.second;
		// 遍历四方向
		for(int i=0;i<4;i++){
			// 计算下一个位置的坐标 (nx,ny) 
			int nx=x+dx[i];
			int ny=y+dy[i];
			// 模拟 (x,y) -> (nx,ny)
			// 判断是否能够走到 (nx,ny)
			if(nx<1 || ny<1 || nx>n || ny>m || vis[nx][ny] || g[nx][ny]==障碍物) continue;
			// 可以走到 (nx,ny)
			vis[nx][ny]=true;
			d[nx][ny]=d[x][y] + 1;
			q.push({nx,ny});
		} 
	}
}

点线图


建图 
vector<int>v[N];
标记数组
bool vis[N];
距离数组
int d[N];
// 模板 
void bfs(int bg){
	queue<int>q;
	// 初始化起点 
	vis[bg]=true;
	d[bg]=0;
	q.push(bg);
	
	while(!q.empty()){
		// 取出队头 
		int t=q.front();
		q.pop();
		
		// 遍历所有相邻节点 
		for(auto x:v[t]){
			// 模拟 t -> x 
			// 判断是否可以走到 x 
			if(vis[x]) continue;
			// 可以走到 x 
			vis[x]=true;
			d[x]=d[t]+1;
			q.push(x);
		}
	}
}

T129443.小试牛刀

//#include<bits/stdc++.h>
using namespace std;
int n,m,u,v,x,dis[111];
vector<int>g[111];
bool vis[111];
void bfs(int begin){
    queue<int>q;
    vis[begin]=true;
    dis[begin]=0;
    q.push(begin);
    while(!q.empty()){
        int t=q.front();
        q.pop();
        for(auto x:g[t]){
            if(vis[x]){
                continue;
            }
            vis[x]=true;
            dis[x]=dis[t]+1;
            q.push(x);
        }
    }
}
int main(){
    cin>>n>>m;
    for(int j=1;j<=m;j++){
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for(int i=1;i<=n;i++){
        dis[i]=-1;
    }
    cin>>x;
    bfs(x);
    for(int i=1;i<=n;i++){
        cout<<dis[i]<<" ";
    }
    return 0;
}

T130027.迷路的小猫

//#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N = 200010;

vector<int>v[N];
bool vis[N];
int d[N];
// 模板 
void bfs(int bg){
	queue<int>q;
	// 初始化起点 
	vis[bg]=true;
	d[bg]=0;
	q.push(bg);
	
	while(!q.empty()){
		// 取出队头 
		int t=q.front();
		q.pop();
		
		// 遍历所有相邻节点 
        for(int x:{t+1,t-1,2*t}){
            if(x>=0 && x<=200000 && !vis[x]){
                vis[x]=true;
                d[x]=d[t]+1;
                q.push(x);
            }
        }

        // x=t-1;
        // if(x>=0 && x<=200000 && !vis[x]){
        //     vis[x]=true;
        //     d[x]=d[t]+1;
        //     q.push(x);
        // }
        
        // x=t*2;
        // if(x>=0 && x<=200000 && !vis[x]){
        //     vis[x]=true;
        //     d[x]=d[t]+1;
        //     q.push(x);
        // }
	}
}

int main(){
	int a,b;cin>>a>>b;
	bfs(a);
    cout<<d[b]<<endl;
	return 0;

T133344.单词接龙

//#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N = 10010;

map<string,vector<string>>v;
map<string,bool>vis;
map<string,int>d;
string s[N];
// 模板 
void bfs(string bg){
	queue<string>q;
	// 初始化起点 
	vis[bg]=true;
	d[bg]=1;
	q.push(bg);
	
	while(!q.empty()){
		// 取出队头 
		string t=q.front();
		q.pop();
		
		// 遍历所有相邻节点 
		for(auto x:v[t]){
			// 模拟 t -> x 
			// 判断是否可以走到 x 
			if(vis[x]) continue;
			// 可以走到 x 
			vis[x]=true;
			d[x]=d[t]+1;
			q.push(x);
		}
	}
}


int main(){
	string a,b;cin>>a>>b;
    int n;cin>>n;
    for(int i=1;i<=n;i++){
        cin>>s[i];
    }
    s[0]=a;
    // 建图
    for(int i=0;i<=n;i++){
        for(int j=0;j<i;j++){
            int cnt=0;
            for(int k=0;k<s[i].size();k++){
                if(s[i][k]!=s[j][k]) cnt++;
            }
            if(cnt==1){
                v[s[i]].push_back(s[j]);
                v[s[j]].push_back(s[i]);
            }
        }
    }

    bfs(a);

    cout<<d[b]<<endl;
    
	return 0;
}

T130063.彩色墨水扩散

注：多源BFS

//#include<bits/stdc++.h>
using namespace std;
int n,m,dis[1111][1111],ans;
char g[1111][1111];
bool vis[1111][1111];
int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};
void bfs(){
    queue<pair<int,int>>q;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(g[i][j]=='#'){
                vis[i][j]=true;
                dis[i][j]=0;
                q.push({i,j});
            }
        }
    }
    while(!q.empty()){
        auto t=q.front();
        q.pop();
        for(int i=0;i<4;i++){
            int nx=t.first+dx[i];
            int ny=t.second+dy[i];
            if(nx<1 || nx>n || ny<1 || ny>m || vis[nx][ny])continue;
            vis[nx][ny]=true;
            dis[nx][ny]=dis[t.first][t.second]+1;
            q.push({nx,ny});
        }
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>g[i][j];
        }
    }
    bfs();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            ans=max(ans,dis[i][j]);
        }
    }
    cout<<ans;
    return 0;
}