广度优先搜索 BFS

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
int n,m,grid[105][105],dist[105][105];
int dx[]={-1,1,0,0},dy[]={0,0,-1,1};
int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++) cin>>grid[i][j];
    memset(dist,-1,sizeof(dist));
    queue<pair<int,int>> q;
    q.push({0,0}); dist[0][0]=0;
    while(!q.empty()){
        auto [x,y]=q.front(); q.pop();
        for(int d=0;d<4;d++){
            int nx=x+dx[d],ny=y+dy[d];
            if(nx>=0&&nx<n&&ny>=0&&ny<m
                &&grid[nx][ny]==0&&dist[nx][ny]==-1){
                dist[nx][ny]=dist[x][y]+1;
                q.push({nx,ny});
            }
        }
    }
    cout<<dist[n-1][m-1]<<endl;
    return 0;
}

#include <iostream>
#include <queue>
using namespace std;
int n,g[35][35];
bool vis[35][35];
int dx[]={-1,1,0,0},dy[]={0,0,-1,1};
void bfs(int sx,int sy){
    queue<pair<int,int>> q;
    q.push({sx,sy}); vis[sx][sy]=true;
    while(!q.empty()){
        auto [x,y]=q.front(); q.pop();
        for(int d=0;d<4;d++){
            int nx=x+dx[d],ny=y+dy[d];
            if(nx>=0&&nx<n&&ny>=0&&ny<n
                &&g[nx][ny]==0&&!vis[nx][ny]){
                vis[nx][ny]=true;
                q.push({nx,ny});
            }
        }
    }
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++) cin>>g[i][j];
    // 从边界的0出发BFS
    for(int i=0;i<n;i++){
        if(g[i][0]==0&&!vis[i][0]) bfs(i,0);
        if(g[i][n-1]==0&&!vis[i][n-1]) bfs(i,n-1);
    }
    for(int j=0;j<n;j++){
        if(g[0][j]==0&&!vis[0][j]) bfs(0,j);
        if(g[n-1][j]==0&&!vis[n-1][j]) bfs(n-1,j);
    }
    // 输出：未标记的0改为2
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(g[i][j]==0&&!vis[i][j]) cout<2;
            else cout<<g[i][j];
            cout<" ";
        }
        cout<<endl;
    }
    return 0;
}

#include <iostream>
#include <queue>
#include <map>
#include <string>
using namespace std;
string ruleA[10],ruleB[10];
int cnt=0;
int bfs(string start,string target){
    queue<pair<string,int>> q;
    map<string,bool> vis;
    q.push({start,0}); vis[start]=true;
    while(!q.empty()){
        auto [s,step]=q.front(); q.pop();
        if(s==target) return step;
        if(step>=10) continue;
        for(int i=0;i<cnt;i++){
            size_t pos=0;
            while((pos=s.find(ruleA[i],pos))!=string::npos){
                string ns=s;
                ns.replace(pos,ruleA[i].length(),ruleB[i]);
                if(!vis[ns]){vis[ns]=true; q.push({ns,step+1});}
                pos++;
            }
        }
    }
    return -1;
}

#include <iostream>
#include <queue>
using namespace std;
int n,m,g[55][55];
int dx[]={-1,1,0,0},dy[]={0,0,-1,1};
int main(){
    cin>>n>>m;
    queue<pair<pair<int,int>,int>> q;
    int fresh=0;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++){
            cin>>g[i][j];
            if(g[i][j]==1) q.push({{i,j},0});
            if(g[i][j]==0) fresh++;
        }
    int ans=0;
    while(!q.empty()){
        auto [pos,t]=q.front(); q.pop();
        auto [x,y]=pos; ans=t;
        for(int d=0;d<4;d++){
            int nx=x+dx[d],ny=y+dy[d];
            if(nx>=0&&nx<n&&ny>=0&&ny<m&&g[nx][ny]==0){
                g[nx][ny]=1; fresh--;
                q.push({{nx,ny},t+1});
            }
        }
    }
    cout<<(fresh==0?ans:-1)<<endl;
    return 0;
}

#include <iostream>
#include <queue>
#include <unordered_set>
#include <string>
using namespace std;
int dx[]={-1,1,0,0},dy[]={0,0,-1,1};
int bfs(string start, string target){
    if(start==target) return 0;
    queue<pair<string,int>> q;
    unordered_set#include <string> vis;
    q.push({start,0}); vis.insert(start);
    while(!q.empty()){
        auto [s,step]=q.front(); q.pop();
        int pos=s.find('0');
        int x=pos/3, y=pos%3;
        for(int d=0;d<4;d++){
            int nx=x+dx[d],ny=y+dy[d];
            if(nx>=0&&nx<3&&ny>=0&&ny<3){
                string ns=s;
                swap(ns[pos],ns[nx*3+ny]);
                if(ns==target) return step+1;
                if(vis.find(ns)==vis.end()){
                    vis.insert(ns);
                    q.push({ns,step+1});
                }
            }
        }
    }
    return -1;
}

#include <iostream>
#include <queue>
#include <set>
using namespace std;
int A,B,C;
int bfs(){
    queue<pair<pair<int,int>,int>> q;
    set<pair<int,int>> vis;
    q.push({{0,0},0}); vis.insert({0,0});
    while(!q.empty()){
        auto [st,step]=q.front(); q.pop();
        auto [a,b]=st;
        if(a==C||b==C) return step;
        // 6种操作
        pair<int,int> nexts[] = {
            {A,b},{a,B},{0,b},{a,0},
            {max(0,a+b-B),min(B,a+b)},
            {min(A,a+b),max(0,a+b-A)}
        };
        for(auto& ns : nexts)
            if(vis.find(ns)==vis.end()){
                vis.insert(ns);
                q.push({ns,step+1});
            }
    }
    return -1;
}

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
int n,k,g[55][55],dist[55][55][12];
int dx[]={-1,1,0,0},dy[]={0,0,-1,1};
struct State{int x,y,c;};
int bfs(){
    memset(dist,-1,sizeof(dist));
    queue<State> q;
    q.push({0,0,0}); dist[0][0][0]=0;
    while(!q.empty()){
        auto [x,y,c]=q.front(); q.pop();
        if(x==n-1&&y==n-1) return dist[x][y][c];
        for(int d=0;d<4;d++){
            int nx=x+dx[d],ny=y+dy[d];
            if(nx>=0&&nx<n&&ny>=0&&ny<n){
                int nc = c + g[nx][ny];
                if(nc<=k && dist[nx][ny][nc]==-1){
                    dist[nx][ny][nc]=dist[x][y][c]+1;
                    q.push({nx,ny,nc});
                }
            }
        }
    }
    return -1;
}