提出 #73588401

---

ソースコード 拡げる

#include <bits/stdc++.h>
#include <atcoder/all>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace atcoder;
using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
#define ALL(a) (a).begin(), (a).end()
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define rrep(i, n) for (ll i = (n) - 1; i >= 0; --i)
#define rep_2(i, j, n) for (ll i = 0; i < (n); ++i) for (ll j = i + 1; j < (n); ++j)
#define foreach(i, n) for (auto& i : (n))
#define chmax(a, b) a = max(a, b)
#define chmin(a, b) a = min(a, b)
#define popcount __builtin_popcountll
#define bitcheck(mask, j) ((mask) & (1LL << (j)))

using mint = modint998244353;
using mint1 = modint1000000007;

template <typename K, typename V>
using umap = std::unordered_map<K, V>;
template <typename K>
using uset = std::unordered_set<K>;

// 参考元 : https://qiita.com/ganyariya/items/df35d253726269bda436
struct HashPair {
    
    //注意 constがいる
    template<class T1, class T2>
    size_t operator()(const pair<T1, T2> &p) const {
        
        //first分をハッシュ化する
        auto hash1 = hash<T1>{}(p.first);
        
        //second分をハッシュ化する
        auto hash2 = hash<T2>{}(p.second);
        
        //重複しないようにハッシュ処理
        size_t seed = 0;
        seed ^= hash1 + 0x9e3779b9 + (seed << 6) + (seed >> 2);
        seed ^= hash2 + 0x9e3779b9 + (seed << 6) + (seed >> 2);
        return seed;
    }
};

template <typename X, typename Y>
using pair_map = unordered_map<X, Y, HashPair>;

template <typename X, typename Y>
using pair_set = unordered_set<pair<X, Y>, HashPair>;

// [left, right) の範囲で f(mid) が true になる最小の left を返す
// 単調性: false...false,true...true
template<class F, class T>
T binary_search_min_left(T left, T right, F f){
    while (right - left > 1){
        T mid = left + (right - left) / 2;
        if(f(mid)) right = mid;
        else left = mid;
    }
    return right;
}

// [left, right) の範囲で f(mid) が true になる最大の right-1 を返す
// 単調性: true...true,false...false
template<class F, class T>
T binary_search_max_right(T left, T right, F f){
    while (right - left > 1){
        T mid = left + (right - left) / 2;
        if(f(mid)) left = mid;
        else right = mid;
    }
    return left;
}

template <typename T>
using v = vector<T>;
template <typename T>
using vv = v<v<T>>;
template <typename T>
using vvv = vv<v<T>>;

template <typename T, typename U>
using P = pair<T, U>;

using grid = vector<vector<char>>;
using graph = vector<vector<int>>;
using vi = vector<int>; using vvi = vector<vector<int>>; using vvvi = vector<vector<vector<int>>>;
using vl = vector<ll>; using vvl = vector<vector<ll>>; using vvvl = vector<vector<vector<ll>>>;
using vm = vector<mint>; using vvm = vector<vector<mint>>; using vvvm = vector<vector<vector<mint>>>;
using vm1 = vector<mint1>; using vvm1 = vector<vector<mint1>>; using vvvm1 = vector<vector<vector<mint1>>>;
using vld = vector<ld>; using vvld = vector<vector<ld>>; using vvvld = vector<vector<vector<ld>>>;
using vb = vector<bool>; using vvb = vector<vector<bool>>; using vvvb = vector<vector<vector<bool>>>;
using vs = vector<string>; using vvs = vector<vector<string>>;

ll inf = 4e18;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll n, m;
    cin >> n >> m;
    vs s(n);
    rep(i, n) cin >> s[i];
    vvl dist(n, vl(m, inf));
    dist[0][0] = 0;
    deque<P<ll, ll>> q;
    q.push_back({0, 0});
    ll H = n; // 縦
    ll W = m; // 横
    auto isOut = [&](ll i, ll j) {
        return i < 0 || j < 0 || i >= H || j >= W;
    };
    ll dx[] = {1, -1, 0, 0};
    ll dy[] = {0, 0, 1, -1};
    while (!q.empty()) {
        auto [i, j] = q.front();
        q.pop_front();
        rep(k, 4) {
            ll ni = i + dx[k];
            ll nj = j + dy[k];
            if (isOut(ni, nj)) continue;
            ll cost = dist[i][j];
            if (s[ni][nj] == '#') cost++;
            if (dist[ni][nj] > cost) {
                dist[ni][nj] = cost;
                if (s[ni][nj] == '#') q.push_back({ni, nj});
                else q.push_front({ni, nj});
            }
        }
    }
    cout << dist[n - 1][m - 1] << endl;
    return 0;
}

提出情報

ジャッジ結果