Submission #72575063

---

Source Code Expand

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

int main(void){
  vector<int> vx = {-1,0,1,0};
  vector<int> vy = {0,-1,0,1};
  int h,w;
  cin >> h >> w;
  vector<string> s(h);
  for(int i=0;i<h;i++){
    cin >> s.at(i);
  }
  vector<vector<int>> seen(h,vector<int>(w, 1e8));
  seen.at(0).at(0) = 0;
  queue<pair<int,int>> q;
  q.push({0,0});
  while(!q.empty()){
    auto p = q.front();
    q.pop();
    for(int i=0;i<4;i++){
      int x = p.first + vx.at(i);
      int y = p.second + vy.at(i);
      if(x >= 0 && x < h && y >= 0 && y < w && seen.at(x).at(y) > seen.at(p.first).at(p.second) + 1 && s.at(x).at(y) != s.at(p.first).at(p.second)){
        seen.at(x).at(y) = seen.at(p.first).at(p.second) + 1;
        q.push({x,y});
      }
    }
  }
  // for(int i=0;i<h;i++){
  //   for(int j=0;j<w;j++){
  //     cout << seen.at(i).at(j) << ' ';
  //   }
  //   cout << endl;
  // }
  if(seen.at(h-1).at(w-1) == 1e8){
    cout << -1 << endl;
  }else{
    cout << seen.at(h-1).at(w-1) << endl;
  }
  return 0;
}

Submission Info

Judge Result