Submission #71680395

---

Source Code Expand

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <set>
#include <unordered_map>
#include <map>
#include <unordered_set>
#include <queue>
#include <algorithm>
#include <iomanip>
#include <cassert>
#include <functional>
#include <chrono>
#include <random>


using namespace std;
#define ll long long
#define MOD 998244353
#define ld long double
#define INF 2251799813685248
#define vall(A) A.begin(),A.end()
#define gridinput(vv,H,W) for (ll i = 0; i < H; i++){string T; cin >> T; for(ll j = 0; j < W; j++){vv[i][j] = {T[j]};}}
#define adjustedgridinput(vv,H,W) for (ll i = 1; i <= H; i++){string T; cin >> T; for(ll j = 1; j <= W; j++){vv[i][j] = {T[j-1]};}}
#define vin(A) for (ll i = 0, sz = A.size(); i < sz; i++){cin >> A[i];}
#define vout(A) for(ll i = 0, sz = A.size(); i < sz; i++){cout << A[i] << " \n"[i == sz-1];}
#define adjustedvin(A) for (ll i = 1, sz = A.size(); i < sz; i++){cin >> A[i];}
#define adjustedvout(A) for(ll i = 1, sz = A.size(); i < sz; i++){cout << A[i] << " \n"[i == sz-1];}
#define vout2d(A,H,W) for (ll i = 0; i < H; i++){for (ll j = 0; j < W; j++){cout << A[i][j] << " \n"[j==W-1];}}
#define encode(i,j) ((i)<<32)+j
#define decode(v,w) (w ? (v)%4294967296 : (v)>>32)
vector<ll> pow2ll{1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576,2097152,4194304,8388608,16777216,33554432,67108864,134217728,268435456,536870912,1073741824,2147483648,4294967296};
vector<ll> pow10ll{1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000,10000000000,100000000000,1000000000000,10000000000000,100000000000000,1000000000000000,10000000000000000,100000000000000000,1000000000000000000};
vector<ll> di{0,1,0,-1};
vector<ll> dj{1,0,-1,0};




/// @brief a^bをmで割った余りを返す。bに関して対数時間で計算できる。
/// @param a 
/// @param b 
/// @param m 
/// @return a^b%m
ll modpow(ll a, ll b, ll m){
    ll t = a%m;
    ll ans = 1;
    while (b > 0){
        if (b%2){
            ans = (ans*t)%m;
        }
        b /= 2;
        t = (t*t)%m;
    }
    return ans;
}

int main(){
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    ll H,W;
    cin >> H >> W;

    vector<vector<string>> A(H+2,vector<string>(W+2,"#"));
    vector<set<pair<ll,ll>>> tel(26);
    vector<bool> tel_used(26,0);

    for (ll i = 1; i <= H; i++){
        string T;
        cin >> T;
        for (ll j = 1; j <= W; j++){
            A[i][j] = T[j-1];
            if (A[i][j] != "." && A[i][j] != "#"){
                tel[A[i][j][0]-97].insert({i,j});
            }
        }
    }

    queue<pair<ll,ll>> Q;
    vector<vector<ll>> dist(H+2,vector<ll>(W+2, -1));
    dist[1][1] = 0;
    Q.push({1,1});

    while (!Q.empty()){
        ll i = Q.front().first;
        ll j = Q.front().second;

        Q.pop();

        if (A[i][j] == "."){
            for (ll k = 0; k < 4; k++){
                if (A[i+di[k]][j+dj[k]] != "#" && dist[i+di[k]][j+dj[k]] == -1){
                    dist[i+di[k]][j+dj[k]] = dist[i][j]+1;
                    Q.push({i+di[k], j+dj[k]});
                }
            }
            continue;
        }
        else{
            for (ll k = 0; k < 4; k++){//まず歩いてみる
                if (A[i+di[k]][j+dj[k]] != "#" && dist[i+di[k]][j+dj[k]] == -1){
                    dist[i+di[k]][j+dj[k]] = dist[i][j]+1;
                    Q.push({i+di[k], j+dj[k]});
                }
            }
            if (tel_used[A[i][j][0]-'a']){//もし使用済みなら
                continue;
            }
            else{
                tel_used[A[i][j][0]-'a'] = 1;
                for (auto v : tel[A[i][j][0]-'a']){
                    if (v == make_pair(i,j)){continue;}
                    if (dist[v.first][v.second] != -1){continue;}
                    dist[v.first][v.second] = dist[i][j] + 1;
                    Q.push(v);
                }
            }
        }
    }

    cout << dist[H][W] << "\n";

}

Submission Info

Judge Result