Submission #4243109

---

Source Code Expand

#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <chrono>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <tuple>
#include <unordered_map>
#include <vector>
using namespace std;

#define FOR(i,m,n) for(int i=(m);i<(n);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()

const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
/*----------------------------------------*/
const int dy[] = {1, 0, -1, 0}, dx[] = {0, -1, 0, 1};

vector<vector<int> > bfs(const vector<vector<char> > &board, int sy, int sx) {
  const int height = board.size(), width = board.front().size();
  vector<vector<int> > dist(height, vector<int>(width, -1));
  dist[sy][sx] = 0;
  queue<pair<int, int>> que;
  que.push({sy, sx});
  while (!que.empty()) {
    pair<int, int> pr = que.front(); que.pop();
    REP(i, 4) {
      int y = pr.first + dy[i], x = pr.second + dx[i];
      if (0 <= y && y < height && 0 <= x && x < width && dist[y][x] == -1 && board[y][x] != '#') {
        dist[y][x] = dist[pr.first][pr.second] + 1;
        que.push({y, x});
      }
    }
  }
  return dist;
}

int main() {
  cin.tie(0); ios::sync_with_stdio(false);
  // freopen("input.txt", "r", stdin);

  int n, m; cin >> n >> m;
  vector<vector<char> > s(n, vector<char>(m));
  int sy, sx, cy, cx, gy, gx;
  REP(i, n) REP(j, m) {
    cin >> s[i][j];
    if (s[i][j] == 'S') {
      sy = i; sx = j;
    } else if (s[i][j] == 'C') {
      cy = i; cx = j;
    } else if (s[i][j] == 'G') {
      gy = i; gx = j;
    }
  }
  vector<vector<int> > s2c = bfs(s, sy, sx), c2g = bfs(s, cy, cx);
  if (s2c[cy][cx] == -1 || c2g[gy][gx] == -1) {
    cout << -1 << '\n';
    return 0;
  }
  cout << s2c[cy][cx] + c2g[gy][gx] << '\n';
  return 0;
}

Submission Info

Judge Result