Submission #162405

---

Source Code Expand

#include <iostream>
#include <queue>

using namespace std;

int main() {
  int R, C, sx, sy, gx, gy;
  int map[60][60] = {};
  cin >> R >> C >> sx >> sy >> gx >> gy;
  sx--; sy--; gx--; gy--;
  int dx[] = {-1, 1, 0, 0};
  int dy[] = {0, 0, -1, 1};

  for (int i = 0; i < R; i++) {
    string s;
    cin >> s;
    for (int j = 0; j < C; j++) {
      if (s[j] == '.') {
	map[i][j] = 99999;
      } else {
	map[i][j] = -1;
      }
    }
  }

  queue <pair<int, int> > q;
  map[sx][sy] = 0;
  q.push(make_pair(sy, sx));

  while(!q.empty()) {
    int cx = q.front().first, cy = q.front().second;
    q.pop();
    int dist = map[cx][cy];
    if (cx == gx && cy== gy) {
      cout << dist << endl;
      break;
    }

    //    cout << cx << " " << cy << " " << dist << endl;
    for (int i = 0; i < 4; i++) {
      int nx = cx + dx[i], ny = cy + dy[i];
      if (map[nx][ny] <= dist + 1) continue;
      map[nx][ny] = dist + 1;
      q.push(make_pair(nx, ny));
    }
  }

  return 0;
}

Submission Info

Judge Result