Contest Duration: ~ (local time)

Submission #2039448

Source Code Expand

Copy
```#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cctype>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<stdlib.h>
#include<iomanip>

using namespace std;

#define ll long long
#define ld long double
#define EPS 0.0000000001
#define INF 1e9
#define MOD 1000000007
#define rep(i,n) for(i=0;i<(n);i++)
#define loop(i,a,n) for(i=a;i<(n);i++)
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)

typedef vector<int> vi;
typedef pair<int,int> pii;

int used[2][300][300];
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
char g[300][300];
int h,w;

void dfs(int x, int y, int d){
used[d][x][y]++;
if(g[x][y]=='#')return;
int i;
rep(i,4){
int nx=x+dx[i];
int ny=y+dy[i];
if(nx>=0 && nx<h && ny>=0 && ny<w && used[d][nx][ny]==0)dfs(nx,ny,d);
}
}

int main(void) {
int i,j;

cin>>h>>w;
rep(i,h)cin>>g[i];

int sx,sy,gx,gy;
rep(i,h)rep(j,w)
if(g[i][j]=='S'){
sx=i;sy=j;
}else if(g[i][j]=='G'){
gx=i;gy=j;
}
dfs(sx,sy,0);
dfs(gx,gy,1);
int ans=0;
rep(i,h)rep(j,w)
if(g[i][j]=='#' && used[0][i][j] && used[1][i][j]){
g[i][j]='.';
queue<pii> q;
q.push(pii(sx,sy));
vector<vi> d(300,vi(300,INF));
d[sx][sy]=0;
while(q.size()){
int x=q.front().first;
int y=q.front().second;
q.pop();
if(x==gx && y==gy)break;
int k;
rep(k,4){
int nx=x+dx[k];
int ny=y+dy[k];
if(nx>=0 && nx<h && ny>=0 && ny<w && g[nx][ny]!='#' && d[x][y]+1 < d[nx][ny]){
d[nx][ny]=d[x][y]+1;
q.push(pii(nx,ny));
}
}
}
ans=max(ans,d[gx][gy]);
g[i][j]='#';
}
cout<<ans<<endl;
}
```

#### Submission Info

Submission Time 2018-01-29 23:27:02+0900 A - 不完全迷路 rika0384 C++14 (GCC 5.4.1) 0 1837 Byte TLE

#### Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample_1, sample_2, sample_3, sample_4, sample_5
All 0 / 100 sample_1, sample_2, sample_3, sample_4, sample_5, large_1, large_2, large_3, large_4, large_5, large_6, medium_00, medium_01, medium_02, medium_03, medium_04, medium_05, medium_06, medium_07, medium_10, medium_11, medium_12, medium_13, medium_14, medium_15, medium_16, medium_17, random_1, random_2, random_3, random_4, random_5, sample_1, sample_2, sample_3, sample_4, sample_5, small_1, small_2
Case Name Status Exec Time Memory
large_1 131 ms 1472 KB
large_2 4 ms 640 KB
large_3 11 ms 5264 KB
large_4 11 ms 5264 KB
large_5
large_6 123 ms 3520 KB
medium_00 2 ms 656 KB
medium_01 1 ms 656 KB
medium_02 1 ms 656 KB
medium_03 1 ms 656 KB
medium_04 1 ms 656 KB
medium_05 1 ms 656 KB
medium_06 2 ms 656 KB
medium_07 1 ms 656 KB
medium_10 2 ms 672 KB
medium_11 2 ms 688 KB
medium_12 2 ms 672 KB
medium_13 2 ms 688 KB
medium_14 2 ms 688 KB
medium_15 2 ms 688 KB
medium_16 2 ms 688 KB
medium_17 2 ms 688 KB
random_1 134 ms 1216 KB
random_2 15 ms 944 KB
random_3 4 ms 912 KB
random_4 170 ms 1216 KB
random_5 355 ms 1312 KB
sample_1 2 ms 672 KB
sample_2 2 ms 672 KB
sample_3 1 ms 640 KB
sample_4 2 ms 672 KB
sample_5 2 ms 672 KB
small_1 2 ms 656 KB
small_2 1 ms 656 KB