src/graph/grid_bfs.hpp

View this file on GitHub
Last update: 2025-12-30 15:03:15+09:00
Include: #include "src/graph/grid_bfs.hpp"

Depends on

src/template.hpp

Code

#include "../template.hpp"

vector<vector<int>> grid_bfs(vector<string>& S,int sy,int sx){
    vector<int> dd={0,1,0,-1,0};
    int H=si(S);
    int W=si(S[0]);
    vector dp(H,vector<int>(W,1e9));
    queue<pair<int,int>> q;
    dp[sy][sx]=0;
    q.push({sy,sx});
    while(si(q)){
        auto [y,x]=q.front();
        q.pop();
        rep(i,4){
            int ny=y+dd[i];
            int nx=x+dd[i+1];
            if(ny<0||H<=ny||nx<0||W<=nx) continue;
            if(dp[ny][nx]!=1e9) continue;
            if(S[ny][nx]=='#') continue;
            dp[ny][nx]=dp[y][x]+1;
            q.push({ny,nx});
        }
    }
    return dp;
};

#line 2 "src/template.hpp"
#include <bits/stdc++.h>
using namespace std;
#define si(a) (long)a.size()
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<(int)(n);++i)
template<typename S,typename F> bool chmin(S&a,F b){return b<a?(a=b,1):0;}
template<typename S,typename F> bool chmax(S&a,F b){return b>a?(a=b,1):0;}
bool _=(ios::sync_with_stdio(0),cin.tie(0),cout<<fixed<<setprecision(16),0);
#line 2 "src/graph/grid_bfs.hpp"

vector<vector<int>> grid_bfs(vector<string>& S,int sy,int sx){
    vector<int> dd={0,1,0,-1,0};
    int H=si(S);
    int W=si(S[0]);
    vector dp(H,vector<int>(W,1e9));
    queue<pair<int,int>> q;
    dp[sy][sx]=0;
    q.push({sy,sx});
    while(si(q)){
        auto [y,x]=q.front();
        q.pop();
        rep(i,4){
            int ny=y+dd[i];
            int nx=x+dd[i+1];
            if(ny<0||H<=ny||nx<0||W<=nx) continue;
            if(dp[ny][nx]!=1e9) continue;
            if(S[ny][nx]=='#') continue;
            dp[ny][nx]=dp[y][x]+1;
            q.push({ny,nx});
        }
    }
    return dp;
};