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
Task A - 不完全迷路
User rika0384
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1837 Byte
Status

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