Submission #61392722

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
#define int long long
#define f(i,j,n) for(int i=j;i<=n;i++)
#define F(i,n,j) for(int i=n;i>=j;i--)
#define updmax(a,b) a=max(a,b)
#define updmin(a,b) a=min(a,b)
#define pb push_back
#define XQZ
using namespace std;
namespace fsd{
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXSIZE,stdin),p1==p2)?EOF:*p1++)
  const int MAXSIZE=1<<20;
  char buf[MAXSIZE],*p1,*p2;
  inline int read(){
    int ak=0,ioi=1;char c=gc();
    while(!isdigit(c)){if(c=='-')ioi=-1;c=gc();}
    while(isdigit(c))ak=ak*10+(c^48),c=gc();
    return ak*ioi;
  }
  inline string reads(){
    string o="";
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include<bits/stdc++.h>
#define int long long
#define f(i,j,n) for(int i=j;i<=n;i++)
#define F(i,n,j) for(int i=n;i>=j;i--)
#define updmax(a,b) a=max(a,b)
#define updmin(a,b) a=min(a,b)
#define pb push_back
#define XQZ
using namespace std;
namespace fsd{
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXSIZE,stdin),p1==p2)?EOF:*p1++)
	const int MAXSIZE=1<<20;
	char buf[MAXSIZE],*p1,*p2;
	inline int read(){
		int ak=0,ioi=1;char c=gc();
		while(!isdigit(c)){if(c=='-')ioi=-1;c=gc();}
		while(isdigit(c))ak=ak*10+(c^48),c=gc();
		return ak*ioi;
	}
	inline string reads(){
		string o="";
		char p=gc();
		while(p>'z'||p<'a'){p=gc();}
		while(p<='z'&&p>='a'){o+=p;p=gc();}
		return o;
	}
	inline char readc(){
		char p=gc();
		while(!((p<='z'&&p>='a')||(p<='Z'&&p>='A'))){p=gc();}
		return p;
	}
	inline long double readd(){
		long double ak=0;int ioi=1;char c=gc();
		while(!isdigit(c)){if(c=='-')ioi=-1;c=gc();}
		while(isdigit(c))ak*=10,ak+=c-'0',c=gc();
		c=gc();
		long double q=0.1;
		while(isdigit(c))ak+=(c-'0')*q,q*=0.1,c=gc();
		return ak*ioi;
	}
}
using namespace fsd;
int n,m;
bool vis[2][1010][1010];
int d[2][1010][1010];
char a[1010][1010];
int h[3][3]={{1,0},{-1,0}};
int s[3][3]={{0,1},{0,-1}};
queue<pair<int,pair<int,int> > >q;
void gs(){
	cin>>n>>m;
	f(i,1,n)f(j,1,m)cin>>a[i][j],d[0][i][j]=d[1][i][j]=LLONG_MAX/2;
	int x,y;
	f(i,1,n)f(j,1,m)if(a[i][j]=='S')x=i,y=j;
	int sx,sy;
	f(i,1,n)f(j,1,m)if(a[i][j]=='G')sx=i,sy=j;
	q.push({0,{x,y}});
	q.push({1,{x,y}});
	vis[0][x][y]=vis[1][x][y]=1;
	d[0][x][y]=d[1][x][y]=0;
	while(!q.empty()){
		int t=q.front().first,x=q.front().second.first,y=q.front().second.second;
		q.pop();
		if(t==0){
			f(i,0,1){
				int nx=x+h[i][0],ny=y+h[i][1];
				if(nx<=n&&nx>=1&&ny<=m&&ny>=1&&a[nx][ny]!='#'&&!vis[1][nx][ny]){
					vis[1][nx][ny]=1;
					d[1][nx][ny]=d[0][x][y]+1;
					q.push({1,{nx,ny}});
				}
			}
		}else{
			f(i,0,1){
				int nx=x+s[i][0],ny=y+s[i][1];
				if(nx<=n&&nx>=1&&ny<=m&&ny>=1&&a[nx][ny]!='#'&&!vis[0][nx][ny]){
					vis[0][nx][ny]=1;
					d[0][nx][ny]=d[1][x][y]+1;
					q.push({0,{nx,ny}});
				}
			}
		}
	}
	int qr=min(d[0][sx][sy],d[1][sx][sy]);
	cout<<(qr==LLONG_MAX/2?-1:qr)<<endl;
}
signed main(){
#ifndef XQZ
	freopen(".in","r",stdin);
	freopen(".out","w",stdout);
#endif
#ifdef NXD
	int t=0;cin>>t;while(t--)
#endif
		gs();
	return 0;
}

Submission Info

Judge Result