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
Task A - 不完全迷路
User rika0384
Language C++14 (GCC 5.4.1)
Score 100
Code Size 3342 Byte
Status
Exec Time 6 ms
Memory 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