Submission #4239219

---

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[701][710];
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

Judge Result