Submission #1493617
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 = 1e8;
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(ans >= INF){
cout << -1 << endl;
}
else{
cout << ans << endl;
}
return 0;
}
Submission Info
Submission Time |
|
Task |
C - 自宅からの脱出 |
User |
gigime |
Language |
C++14 (GCC 5.4.1) |
Score |
100 |
Code Size |
1354 Byte |
Status |
AC |
Exec Time |
18 ms |
Memory |
1536 KB |
Judge Result
Set Name |
All |
Score / Max Score |
100 / 100 |
Status |
|
Set Name |
Test Cases |
All |
input_0.txt, input_1.txt, input_10.txt, input_11.txt, input_12.txt, input_13.txt, input_14.txt, input_15.txt, input_16.txt, input_17.txt, input_18.txt, input_19.txt, input_2.txt, input_20.txt, input_21.txt, input_22.txt, input_23.txt, input_3.txt, input_4.txt, input_5.txt, input_6.txt, input_7.txt, input_8.txt, input_9.txt |
Case Name |
Status |
Exec Time |
Memory |
input_0.txt |
AC |
2 ms |
1280 KB |
input_1.txt |
AC |
2 ms |
1280 KB |
input_10.txt |
AC |
2 ms |
1280 KB |
input_11.txt |
AC |
2 ms |
1280 KB |
input_12.txt |
AC |
2 ms |
1280 KB |
input_13.txt |
AC |
2 ms |
1280 KB |
input_14.txt |
AC |
13 ms |
1536 KB |
input_15.txt |
AC |
18 ms |
1536 KB |
input_16.txt |
AC |
9 ms |
1408 KB |
input_17.txt |
AC |
18 ms |
1536 KB |
input_18.txt |
AC |
2 ms |
1280 KB |
input_19.txt |
AC |
2 ms |
1280 KB |
input_2.txt |
AC |
1 ms |
1280 KB |
input_20.txt |
AC |
2 ms |
1280 KB |
input_21.txt |
AC |
17 ms |
1536 KB |
input_22.txt |
AC |
10 ms |
1536 KB |
input_23.txt |
AC |
10 ms |
1536 KB |
input_3.txt |
AC |
2 ms |
1280 KB |
input_4.txt |
AC |
1 ms |
1280 KB |
input_5.txt |
AC |
1 ms |
1280 KB |
input_6.txt |
AC |
2 ms |
1280 KB |
input_7.txt |
AC |
2 ms |
1280 KB |
input_8.txt |
AC |
2 ms |
1280 KB |
input_9.txt |
AC |
2 ms |
1280 KB |