Submission #6911487

---

Source Code Expand

#include <algorithm>
#include <iostream>
#include <queue>
#include <string>
#include <vector>

using namespace std;

const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

int main() {
  int R, C;
  cin >> R >> C;
  int s[2];
  cin >> s[0] >> s[1];
  s[0] -= 1;  // 0-origin
  s[1] -= 1;
  int g[2];
  cin >> g[0] >> g[1];
  g[0] -= 1;  // 0-origin
  g[1] -= 1;

  // mapへの代入
  vector<vector<char>> map;
  for (int i = 0; i < R; ++i) {
    vector<char> map_line(C);
    for (int j = 0; j < C; ++j) {
      cin >> map_line[j];
    }
    map.push_back(map_line);
  }
  vector<vector<int>> visited;
  queue<pair<int, int>> tovisit;

  for (int i = 0; i < R; ++i) {
    vector<int> tmp(C, -1);
    visited.push_back(tmp);  // −１で未訪問を表す
  }

  visited[s[0]][s[1]] = 0;
  tovisit.push(make_pair(s[0], s[1]));
  while (!tovisit.empty()) {
    int here[2] = {tovisit.front().first, tovisit.front().second};
    tovisit.pop();

    for (int dir = 0; dir < 4; ++dir) {
      int x = here[0] + dx[dir];
      int y = here[1] + dy[dir];

      if (map[x][y] == '#') continue;
      if (visited[x][y] != -1) continue;  // 訪問済

      visited[x][y] = visited[here[0]][here[1]] + 1;
      tovisit.push(make_pair(x, y));
    }
  }

  cout << visited[g[0]][g[1]] << endl;

  // debug
  // for (int i = 0; i < R; ++i) {
  //   for (int j = 0; j < C; ++j) {
  //     if (visited[i][j] == -1)
  //       cout << "#";  // 壁
  //     else
  //       cout << visited[i][j];
  //     if (j == C - 1) cout << endl;
  //   }
  // }
}

Submission Info

Judge Result