Submission #73588405

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define oke cout << "Yes" << '\n';
#define dame cout << "No" << '\n';
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
using Hai2 = vector<vector<ll>>;
using HaiW = vector<vector<pair<ll,ll>>>;
using HaiB = vector<vector<bool>>;
using Hai3 = vector<vector<vector<ll>>>;

int H,W;
queue<tuple<int,int>>Q;
ll dist [3100][3100];
vector<int>gox = {1,0,-1,0};
vector<int>goy = {0,1,0,-1};
vector<char>goc={'R','D','L','U'};

void bfs(vector<string>&S){
    rep(i,H){
        rep(j,W){
            dist[i][j]=1e9;
        }
    }
    dist[0][0]=0;
    Q.push({0,0});
	
    while(!Q.empty()){
        int x,y;
        tie(y,x) = Q.front();
        Q.pop();
        rep(i,4){
            int xx=x+gox[i],yy=y+goy[i];
            if(xx < 0 || W <= xx || yy < 0 || H <= yy){
                continue;
            }
            if(S[yy][xx] == '#'){
               if(dist[yy][xx]>dist[y][x]+1){
                    dist[yy][xx]=dist[y][x]+1;
                    Q.push({yy,xx});
                }
            }else{
                if(dist[yy][xx]>dist[y][x]){
                    dist[yy][xx]=dist[y][x];
                    Q.push({yy,xx});
                }
            }
        }
    }
}


int main() {
	cout << fixed << setprecision(15);
    cin>>H>>W;
    vector<string>S(H);
    rep(i,H){
        cin>>S[i];
    }
    bfs(S);
    cout<<dist[H-1][W-1]<<endl;
}

Submission Info

Judge Result