Submission #68750733

---

Source Code Expand

#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
const int maxn=500+5;
const int x[4]={-1,0,1,0};
const int y[4]={0,1,0,-1};
string s[maxn];
int dis[maxn][maxn][2];
class A
{
public:
    int x,y,zt;
};
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int h,w;
    cin>>h>>w;
    queue<A> q;
    pair<int,int> ed;
    for (int i=1;i<=h;i++)
    {
        cin>>s[i];
        s[i]=' '+s[i];
        for (int j=1;j<=w;j++)
        {
            dis[i][j][0]=dis[i][j][1]=1e9;
            if (s[i][j]=='S')
            {
                dis[i][j][0]=0;
                q.push({i,j,0});
                s[i][j]='.';
            }
            else if (s[i][j]=='G')
            {
                ed={i,j};
                s[i][j]='.';
            }
        }
    }
    while(!q.empty())
    {
        auto now=q.front();
        q.pop();
        for (int i=0;i<4;i++)
        {
            int nxtx=now.x+x[i];
            int nxty=now.y+y[i];
            int nxtzt=now.zt;
            if (nxtx>0&&nxtx<=h&&nxty>0&&nxty<=w)
            {
                if (s[nxtx][nxty]=='?')
                    nxtzt^=1;
                if (s[nxtx][nxty]!='#'&&dis[nxtx][nxty][nxtzt]>=1e9)
                {
                    if (nxtzt==0&&s[nxtx][nxty]=='x')
                        continue;
                    if (nxtzt==1&&s[nxtx][nxty]=='o')
                        continue;
                    dis[nxtx][nxty][nxtzt]=dis[now.x][now.y][now.zt]+1;
                    q.push({nxtx,nxty,nxtzt});
                }
            }
        }
    }
    int ans=min(dis[ed.first][ed.second][0],dis[ed.first][ed.second][1]);
    if (ans>=1e9)
        cout<<"-1";
    else
        cout<<ans;
}

Submission Info

Judge Result