Submission #72575171

---

Source Code Expand

#include <bits/stdc++.h>
#include<atcoder/modint>
//#include <boost/multiprecision/cpp_int.hpp>
//#include <boost/multiprecision/cpp_dec_float.hpp>
using namespace std;
using ll=long long;
using ldub=long double;
using str=string;
using tup2=tuple<ll,ll>;
using tup3=tuple<ll,ll,ll>;
using tup4=tuple<ll,ll,ll,ll>;
using tup5=tuple<ll,ll,ll,ll,ll>;
using tup6=tuple<ll,ll,ll,ll,ll,ll>;
using tup7=tuple<ll,ll,ll,ll,ll,ll,ll>;
using tupcl=tuple<char,ll>;
using vec=vector<ll>;
using vec2=vector<vec>;
using vec3=vector<vec2>;
using vec4=vector<vec3>;
using vec5=vector<vec4>;
using vec6=vector<vec5>;
using vecs=vector<str>;
using vecs2=vector<vecs>;
using vecc=vector<char>;
using vecc2=vector<vecc>;
using vect2=vector<tup2>;
using vect3=vector<tup3>;
using vect4=vector<tup4>;
using vect5=vector<tup5>;
using vectcl=vector<tupcl>;
using que=queue<ll>;
using que2=queue<tup2>;
using que3=queue<tup3>;
using que4=queue<tup4>;
using que5=queue<tup5>;
using que6=queue<tup6>;
using que7=queue<tup7>;
using Pque=priority_queue<ll>;
using pque=priority_queue<ll,vec,greater<ll>>;
using Pque2=priority_queue<tup2>;
using pque2=priority_queue<tup2,vect2,greater<tup2>>;
using Pque3=priority_queue<tup3>;
using pque3=priority_queue<tup3,vect3,greater<tup3>>;
using Pque4=priority_queue<tup4>;
using pque4=priority_queue<tup4,vect4,greater<tup4>>;
using Pque5=priority_queue<tup5>;
using pque5=priority_queue<tup5,vect5,greater<tup5>>;
//using namespace boost::multiprecision;
//using lll=cpp_int;
//using longf=cpp_dec_float_100;

#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define ins insert
#define tup make_tuple
#define low lower_bound
#define pops(a) __builtin_popcountll(a)
#define all(v) v.begin(),v.end()
#define perm(v) next_permutation(all(v))
#define INF (ll)4e18
#define Yes cout << "Yes" << endl
#define No cout << "No" << endl
#define YN(f) cout << ((f)?"Yes":"No") << endl

vec2 bfs(ll H,ll W,vecc2 &M,ll sh=0,ll sw=0){
  vec2 dist(H,vec(W,INF));
  vec dh={1,0,-1,0},dw={0,1,0,-1};
  que2 BFS;
  dist[sh][sw]=0;
  BFS.push(tup(sh,sw));
  while(!BFS.empty()){
    auto [h,w]=BFS.front();
    BFS.pop();
    for(ll i=0;i<4;i++){
      ll nh=h+dh[i],nw=w+dw[i];
      if(nh<0||H<=nh||nw<0||W<=nw) continue;
      if(M[nh][nw]!=M[h][w]&&dist[nh][nw]>dist[h][w]+1){
        dist[nh][nw]=dist[h][w]+1;
        BFS.push(tup(nh,nw));
      }
    }
  }
  return dist;
}

int main(){
  ll H,W;
  cin >> H >> W;
  vecc2 M(H,vecc(W));
  for(ll i=0;i<H;i++){
    for(ll j=0;j<W;j++) cin >> M[i][j];
  }
  vec2 dist=bfs(H,W,M,0,0);
  if(dist[H-1][W-1]==INF) cout << -1 << endl;
  else cout << dist[H-1][W-1] << endl;
}

Submission Info

Judge Result