wa 29

ac 37

#include<iostream>
#include<climits>
#include<queue>
using namespace std;
struct node
{
    int x,y,dir,s;
}tmp;
queue<node>q;
bool b[1010][1010];
int main()
{
    char c;
    int n,m,i,j,sx,sy,ex,ey,x = 0,y = 0,sum=0,ans=INT_MAX;
    cin>>n>>m;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
        {
            cin>>c;
            if(c=='S')
            {
                sx=i;
                sy=j;
            }
            if(c=='G')
            {
                ex=i;
                ey=j;
            }
            if(c=='#')
                b[i][j]=1;
        }
    q.push({sx,sy,0,0});
    b[sx][sy]=1;
    while(!q.empty())
    {
        tmp=q.front();
        q.pop();
        if(tmp.x==ex&&tmp.y==ey)
        {
            sum++;
            ans=min(ans,tmp.s);
            if(sum>1) cout<<ans;
            return 0;
        }
        for(i=1;i<=4;i++)
            if(i!=tmp.dir)
            {
                switch(i)
                {
                    case 1:
                        x=tmp.x+1;
                        y=tmp.y;
                        break;
                    case 2:
                        x=tmp.x-1;
                        y=tmp.y;
                        break;
                    case 3:
                        x=tmp.x;
                        y=tmp.y+1;
                        break;
                    case 4:
                        x=tmp.x;
                        y=tmp.y-1;
                        break;
                }
                if(x>0&&x<=n&&y>0&&y<=m&&!b[x][y])
                {
                    b[x][y]=1;
                    q.push({x,y,i,tmp.s+1});
                }
            }
    }
    cout<<-1;
    return 0;
}