Submission #1493580

---

Source Code Expand

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

#define FOR(i,l,r) for(int i = int(l);i < int(r);i++)
template<typename T> bool chmax(T& a,const T& b){ return a < b ? (a = b,true) : false; }
template<typename T> bool chmin(T& a,const T& b){ return b < a ? (a = b,true) : false; }
typedef long long ll;

int N,M;
const int MAX_N = 500;
vector<string> S;
int minCost [MAX_N] [MAX_N];
const int INF = 1e9;
const int dx [] = {0,1,0,-1};
const int dy [] = {-1,0,1,0};

int main()
{
	cin >> N >> M;
	S.assign(N,"");
	FOR(i,0,N){
		cin >> S [i];
	}

	fill(minCost [0],minCost [MAX_N],INF);
	queue<int> q;
	FOR(i,0,N) FOR(j,0,M) if(S [i] [j] == 'C'){
		minCost [i] [j] = 0;
		q.push(i * M + j);
	}

	while(q.empty() == false){
		int y = q.front() / M,x = q.front() % M;
		q.pop();

		FOR(i,0,4){
			int ny = y + dy [i],nx = x + dx [i];
			if((ny >= 0 && ny < N && nx >= 0 && nx < M) == false) continue;
			if(S [ny] [nx] == '#' || minCost [ny] [nx] <= minCost [y] [x] + 1) continue;
			minCost [ny] [nx] = minCost [y] [x] + 1;
			q.push(ny * M + nx);
		}
	}

	int ans = 0;
	FOR(i,0,N) FOR(j,0,M){
		if(S [i] [j] == 'S'){
			ans += minCost [i] [j];
		}
		if(S [i] [j] == 'G'){
			ans += minCost [i] [j];
		}
	}

	if(true){
		cout << -1 << endl;
	}
	else{
		cout << ans << endl;
	}

	return 0;
}

Submission Info

Judge Result