Submission #4239208
Source Code Expand
#include<bits/stdc++.h>
using namespace std;
char did;
#define ak *
#define re register int
inline int read() {
re ioi=1,cz=0;
did=getchar();
while(!isdigit(did))
ioi=did=='-'?-1:ioi,did=getchar();
while(isdigit(did))
cz=(cz<<3)+(cz<<1)+did-'0',did=getchar();
return cz ak ioi; //不要管
}
char g[501][510];
int n,m;
int ci,cj,gi,gj,si,sj;
int dx[4]= {1,0,-1,0};
int dy[4]= {0,1,0,-1};
bool vis[501][501];
int Ans=0,tmp1=0x3f3f3f3f,tmp2=0x3f3f3f3f;
inline bool judge(int x,int y) {
if(x>=1&&x<=n&&y>=1&&y<=m) return true;
else return false;
}
void dfs1(int x,int y,int ans) {
int nx,ny;
if(x==ci&&y==cj)
if(ans<tmp1)
tmp1=ans;
if(x<1||y<1||x>m||y>n||g[x][y]=='#') return;
for(int i=0; i<4; i++) {
nx=x+dx[i],ny=y+dy[i];
if(g[nx][ny]!='#'&&judge(nx,ny)&&vis[nx][ny]==0) {
vis[x][y]=1;
dfs1(nx,ny,ans+1);
vis[x][y]=0;
}
}
}
void dfs2(int x,int y,int ans) {
int nx,ny;
if(x==gi&&y==gj)
if(ans<tmp2)
tmp2=ans;
if(x<1||y<1||x>m||y>n||g[x][y]=='#') return;
for(int i=0; i<4; i++) {
nx=x+dx[i],ny=y+dy[i];
if(g[nx][ny]!='#'&&judge(nx,ny)&&!vis[nx][ny]) {
vis[x][y]=1;
dfs2(nx,ny,ans+1);
vis[x][y]=0;
}
}
}
int main() {
n=read(),m=read();
for(int i=1; i<=n; i++) {
for(int j=1; j<=m; j++) {
cin>>g[i][j];
if(g[i][j]=='S') {
si=i;
sj=j;
}
if(g[i][j]=='C') {
ci=i;
cj=j;
}
if(g[i][j]=='G') {
gi=i;
gj=j;
}
}
}
memset(vis,0,sizeof(vis));
dfs1(si,sj,0);
if(tmp1!=0x3f3f3f3f) Ans+=tmp1;
else {
cout<<-1<<endl;
return 0;
}
memset(vis,0,sizeof(vis));
dfs2(ci,cj,0);
if(tmp2!=0x3f3f3f3f) Ans+=tmp2;
else {
cout<<-1<<endl;
return 0;
}
cout<<Ans<<endl;
}
Submission Info
Submission Time |
|
Task |
C - 自宅からの脱出 |
User |
luogu_bot4 |
Language |
C++ (GCC 5.4.1) |
Score |
0 |
Code Size |
1759 Byte |
Status |
WA |
Exec Time |
2104 ms |
Memory |
11776 KB |
Judge Result
Set Name |
All |
Score / Max Score |
0 / 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 |
1 ms |
512 KB |
input_1.txt |
AC |
1 ms |
512 KB |
input_10.txt |
AC |
1 ms |
512 KB |
input_11.txt |
WA |
1 ms |
512 KB |
input_12.txt |
WA |
1 ms |
512 KB |
input_13.txt |
WA |
2 ms |
768 KB |
input_14.txt |
AC |
21 ms |
6528 KB |
input_15.txt |
TLE |
2103 ms |
896 KB |
input_16.txt |
TLE |
2103 ms |
640 KB |
input_17.txt |
TLE |
2103 ms |
768 KB |
input_18.txt |
TLE |
2103 ms |
1024 KB |
input_19.txt |
TLE |
2103 ms |
1024 KB |
input_2.txt |
AC |
1 ms |
512 KB |
input_20.txt |
TLE |
2103 ms |
512 KB |
input_21.txt |
TLE |
2104 ms |
11776 KB |
input_22.txt |
AC |
15 ms |
768 KB |
input_23.txt |
AC |
15 ms |
768 KB |
input_3.txt |
AC |
1 ms |
512 KB |
input_4.txt |
AC |
1 ms |
512 KB |
input_5.txt |
AC |
3 ms |
512 KB |
input_6.txt |
TLE |
2103 ms |
512 KB |
input_7.txt |
TLE |
2103 ms |
512 KB |
input_8.txt |
AC |
1 ms |
512 KB |
input_9.txt |
AC |
1 ms |
512 KB |