Contest Duration: ~ (local time)

Submission #2107477

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 cost[2][300][300];

int main(void) {
int i,j;
int h,w;
cin>>h>>w;
char g[300][300];
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;
}
cost[0][i][j]=INF;
cost[1][i][j]=INF;
}

cost[0][sx][sy]=cost[1][gx][gy]=1;

int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};

queue<pii>q;
q.push(pii(sx,sy));
while(q.size()){
int x=q.front().first;
int y=q.front().second;
q.pop();
rep(i,4){
int nx=x+dx[i];
int ny=y+dy[i];
if(nx>=0 && nx<h && ny>=0 && ny<w && g[nx][ny]!='#' && cost[0][nx][ny] > cost[0][x][y]+1){
cost[0][nx][ny]=cost[0][x][y]+1;
q.push(pii(nx,ny));
}
}
}

q.push(pii(gx,gy));
while(q.size()){
int x=q.front().first;
int y=q.front().second;
q.pop();
rep(i,4){
int nx=x+dx[i];
int ny=y+dy[i];
if(nx>=0 && nx<h && ny>=0 && ny<w && g[nx][ny]!='#' && cost[1][nx][ny] > cost[1][x][y]+1){
cost[1][nx][ny]=cost[1][x][y]+1;
q.push(pii(nx,ny));
}
}
}

int ans=0;
rep(i,h)rep(j,w)if(g[i][j]=='#'){
int tmp=INF;

if(j>0 && cost[0][i][j-1]!=INF){//left
if(j<w-1 && cost[1][i][j+1]!=INF){
tmp=min(tmp,cost[0][i][j-1]+cost[1][i][j+1]);
}
if(i>0 && cost[1][i-1][j]!=INF){
tmp=min(tmp,cost[0][i][j-1]+cost[1][i-1][j]);
}
if(i<h-1 && cost[1][i+1][j]!=INF){
tmp=min(tmp,cost[0][i][j-1]+cost[1][i+1][j]);
}
}

if(j<w-1 && cost[0][i][j+1]!=INF){//right
if(j>0 && cost[1][i][j-1]!=INF){
tmp=min(tmp,cost[0][i][j+1]+cost[1][i][j-1]);
}
if(i>0 && cost[1][i-1][j]!=INF){
tmp=min(tmp,cost[0][i][j+1]+cost[1][i-1][j]);
}
if(i<h-1 && cost[1][i+1][j]!=INF){
tmp=min(tmp,cost[0][i][j+1]+cost[1][i+1][j]);
}
}

if(i>0 && cost[0][i-1][j]!=INF){//top
if(j>0 && cost[1][i][j-1]!=INF){
tmp=min(tmp,cost[0][i-1][j]+cost[1][i][j-1]);
}
if(j<w-1 && cost[1][i][j+1]!=INF){
tmp=min(tmp,cost[0][i-1][j]+cost[1][i][j+1]);
}
if(i<h-1 && cost[1][i+1][j]!=INF){
tmp=min(tmp,cost[0][i-1][j]+cost[1][i+1][j]);
}
}

if(i<h-1 && cost[0][i+1][j]!=INF){//bottom
if(j>0 && cost[1][i][j-1]!=INF){
tmp=min(tmp,cost[0][i+1][j]+cost[1][i][j-1]);
}
if(j<w-1 && cost[1][i][j+1]!=INF){
tmp=min(tmp,cost[0][i+1][j]+cost[1][i][j+1]);
}
if(i>0 && cost[1][i-1][j]!=INF){
tmp=min(tmp,cost[0][i+1][j]+cost[1][i-1][j]);
}
}
if(tmp<INF)ans=max(ans,tmp);
}

cout<<ans<<endl;
}

#### Submission Info

Submission Time 2018-02-18 18:51:54+0900 A - 不完全迷路 rika0384 C++14 (GCC 5.4.1) 100 3342 Byte AC 6 ms 1024 KB

#### Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample_1, sample_2, sample_3, sample_4, sample_5
All 100 / 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 6 ms 1024 KB
large_2 5 ms 1024 KB
large_3 6 ms 1024 KB
large_4 6 ms 1024 KB
large_5 6 ms 1024 KB
large_6 6 ms 1024 KB
medium_00 1 ms 256 KB
medium_01 1 ms 256 KB
medium_02 1 ms 256 KB
medium_03 1 ms 256 KB
medium_04 1 ms 256 KB
medium_05 1 ms 256 KB
medium_06 1 ms 256 KB
medium_07 1 ms 256 KB
medium_10 1 ms 256 KB
medium_11 1 ms 256 KB
medium_12 1 ms 256 KB
medium_13 1 ms 256 KB
medium_14 1 ms 256 KB
medium_15 1 ms 256 KB
medium_16 1 ms 256 KB
medium_17 1 ms 256 KB
random_1 4 ms 768 KB
random_2 3 ms 640 KB
random_3 3 ms 640 KB
random_4 6 ms 1024 KB
random_5 5 ms 896 KB
sample_1 1 ms 256 KB
sample_2 1 ms 256 KB
sample_3 1 ms 256 KB
sample_4 1 ms 256 KB
sample_5 1 ms 256 KB
small_1 1 ms 256 KB
small_2 1 ms 256 KB