Submission #11416205

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;
 
typedef long long ll;
typedef long double ld;
 
#define REP(i,a,n) for(int (i)=(a); (i)<(int)(n); (i)++)
#define rep(i,n) REP(i,0,n)
#define vec vector 

const ll large_P = 1e9 + 7;


int main(){
  int R, C;
  cin >> R >> C;
  
  int sy, sx;
  cin >> sy >> sx;
  sy--; sx--;
  
  int gy, gx;
  cin >> gy >> gx;
  gy--; gx--;
  
  vector<string> c(R);
  rep(i, R) cin >> c.at(i);
  
  vector<vector<int>> dist(R, vector<int>(C, -1)); // 全頂点を「未訪問」に初期化
  queue<pair<int, int>> que;  //その時点での橙色頂点 (発見済みだが未訪問な頂点) を格納するキュー

  dist.at(sy).at(sx) = 0;
  que.push(make_pair(sy, sx));
  
  //BFS
  while(!que.empty()){
    pair<int, int> v = que.front(); que.pop(); // キューから先頭頂点を取り出す
    
    // v から辿れる頂点をすべて調べる
    for(int i = -1; i<=1; i++){
      for(int j = -1; j<=1; j++){
        if(i*j != 0) continue; //本来はいけない場所
        if(v.first + i < 0 || v.first + i >= R) continue;
        if(v.second + j < 0 || v.second + j >= C) continue;
        if(dist.at(v.first+i).at(v.second + j) != -1) continue;
        if(c.at(v.first+i).at(v.second + j) == '#') continue;
        
        dist.at(v.first+i).at(v.second + j) = dist.at(v.first).at(v.second) + 1;
        que.push(make_pair(v.first+i, v.second+j));
      }
    }
  }
  
  cout << dist.at(gy).at(gx) << endl;
  //rep(i, R){
    //rep(j, C){
      //cout << dist.at(i).at(j) << " ";
    //}
    //cout << endl;
  //}
  
  
  
}

Submission Info

Judge Result