Submission #72575118

---

Source Code Expand

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

using ll = long long;
using ld = long double;
#define rep(i, n) for(int i = 0; i < (int) (n); i ++)
#define rrep(i, m, n) for(int i = (int) m; i < (int) n; i ++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const int ddx[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const int ddy[8] = {0, 1, 1, 1, 0, -1, -1, -1};

long long gcd(long long a, long long b){
    if(a % b == 0) return b;
    else return gcd(b, a % b);
}

long long lcm(long long a, long long b){
    return a * b / gcd(a, b);
}

template<typename T>
void v_cin(vector<T> &x){
    rep(i, x.size()) cin >> x[i];
}

template<typename T>
void vv_cin(vector<vector<T>> &x){
    rep(i, x.size()) rep(j, x[i].size()) cin >> x[i][j];
}

template <typename T>
void v_cout(vector<T> &x){
    rep(i, x.size()) cout << x[i] << (i < x.size() - 1 ? " " : "\n");
}

template <typename T>
void vv_cout(vector<vector<T>> &x){
    rep(i, x.size()) v_cout(x[i]);
}

// #include <atcoder/all>
// using namespace atcoder;
// using mint = modint998244353;
// using mint = modint1000000007;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int H, W; cin >> H >> W;
    vector<vector<char>> S(H, vector<char> (W));
    vv_cin(S);

    vector<vector<int>> dist(H, vector<int> (W, 1e9));

    queue<pair<int, int>> Q;
    dist[0][0] = 0;
    Q.push({0, 0});
    while(!Q.empty()){
        auto [x, y] = Q.front(); Q.pop();
        rep(d, 4){
            int nx = x + dx[d], ny = y + dy[d];
            if(nx < 0 or nx >= H or ny < 0 or ny >= W){
                continue;
            }
            if(S[x][y] == S[nx][ny]) continue;
            if(dist[nx][ny] < 1e9) continue;
            dist[nx][ny] = dist[x][y] + 1;
            Q.push({nx, ny});
        }
    }

    cout << (dist[H - 1][W - 1] >= 1e9 ? -1 : dist[H - 1][W - 1]) << "\n";
}

Submission Info

Judge Result