提出 #73589106

---

ソースコード 拡げる

#ifndef ONLINE_JUDGE
#define _GLIBCXX_DEBUG
#endif

#include <bits/stdc++.h>
using namespace std;

#include <ranges>

using ll=long long;
using ull=unsigned long long;
using ld=long double;
using pint=pair<int,int>;
using pill=pair<int,ll>;
using pll=pair<ll,ll>;
using plli=pair<ll,int>;
template<typename T1,typename T2> using unmap=unordered_map<T1,T2>;
template<typename T> using unset=unordered_set<T>;
template<typename T> using p_q=priority_queue<T>;
template<typename T> using rp_q=priority_queue<T,vector<T>,greater<T>>;

#define rep(i,j,n) for(int i=(int)(j);i<(int)(n);i++)
#define per(i,j,n) for(int i=(int)(j);i>=(int)(n);i--)

#define rev(a) reverse(a)

#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()

#define yes cout<<"Yes\n"
#define no cout<<"No\n"
#define dame cout<<"-1\n"
#define ENDL cout<<'\n'

#define ep emplace
#define eb emplace_back
#define pob pop_back
#define ef emplace_front
#define pof pop_front

#define fi first
#define se second

const int iinf=2147483647/2;
const ll linf=9223372036854775807/2;
const ld pai=acosl(-1);

const array<int,8> di={1,0,-1,0,-1,1,-1,1};
const array<int,8> dj={0,1,0,-1,-1,1,1,-1};

template<typename T1,typename T2> istream& operator>>(istream &i,pair<T1,T2> &x){
    i>>x.fi>>x.se;
    return i;
}
template<typename T1,typename T2> ostream& operator<<(ostream &o,const pair<T1,T2> &x){
    return o<<x.fi<<' '<<x.se;
}

void lines(int n=10){
    while(n--) cout<<'-';
    cout<<'\n';
}

template<typename T> void vin(T &v,int n=0){
    if(n==0) n=v.size();
    rep(i,0,n) cin>>v[i];
}

template<typename T> void vout(const T &v,string s=" "){
    int n=v.size();
    rep(i,0,n) cout<<v[i]<<(i+1<n ? s:"\n");
}
template<typename T> void vvout(const T &vv,string s=" "){
    int n=vv.size();
    rep(i,0,n) vout(vv[i],s);
}

template<typename T> bool chmax(T &a,const T &b){
    if(a<b){
        a=b;
        return true;
    }
    return false;
}
template<typename T> bool chmin(T &a,const T &b){
    if(a>b){
        a=b;
        return true;
    }
    return false;
}

template<typename T> bool outgrid(const T &i,const T &j,const T &h,const T &w=-1){
    return (i<0 or i>=h or j<0 or j>=(w==-1 ? h:w));
}

//printf("%.20Lf\n",ans);


////////////////////////////////////////////////////////////////////////////////


int solve(){
    int n,m;
    cin>>n>>m;

    vector<string> s(n);
    vin(s);

    deque<pint> dq;
    dq.eb(0,0);
    vector<vector<int>> cnt(n,vector<int>(m,iinf));
    cnt[0][0]=0;
    while(!dq.empty()){
        auto [i,j]=dq.front();
        dq.pof();
        rep(k,0,4){
            int ni=i+di[k],nj=j+dj[k];
            if(outgrid(ni,nj,n,m)) continue;
            if(s[ni][nj]=='#' and chmin(cnt[ni][nj],cnt[i][j]+1)) dq.eb(ni,nj);
            if(s[ni][nj]=='.' and chmin(cnt[ni][nj],cnt[i][j])) dq.ef(ni,nj);
        }
    }
    cout<<cnt[n-1][m-1]<<'\n';

    return 0;
}

int main(){
    int t=1;
    //cin>>t;

    while(t--) solve();

    return 0;
}

提出情報

ジャッジ結果