题目描述
有一个 H行 W 列的网格。用 (i,j) 表示位于第 i 行（从上往下数）第 j 列（从左往右数）的格子。每个格子的状态用字符 Ai,j表示，含义如下：

. ：空格子。
#’ ：障碍格子。
S ：起点格子。
G ：终点格子。
o ：开着的门格子。
x ：关着的门格子。
? ：开关格子。
高桥君可以从当前格子移动到上下左右相邻的格子，但不能移动到障碍格子或关着的门格子，每次移动算一次操作。

而且，每当他走到一个开关格子时，所有开着的门都会变成关着的门，所有关着的门都会变成开着的门。

请判断他是否能从起点出发，最终到达终点；如果能，求出最少需要多少次操作。

约束条件1≤H,W≤5001≤H,W≤500HH 和 WW 是整数。每个 Ai,jAi,j​ 都是 .、#、S、G、o、x、?和Ai,jA i,j中各出现且仅出现一次。输入格式输入从标准输入给出，格式如下：

H
H
W
W
A
1
,
1
A
1
,
2
⋯
A
1
,
W
A
1,1
​
A
1,2
​
⋯A
1,W
​

A
2
,
1
A
2
,
2
⋯
A
2
,
W
A
2,1
​
A
2,2
​
⋯A
2,W
​

⋮
⋮
A
H
,
1
A
H
,
2
⋯
A
H
,
W
A
H,1
​
A
H,2
​
⋯A
H,W
​

输出格式
如果高桥君能从起点移动到终点，输出最少的操作次数；否则输出 -1。

样例 1
Input
2 4
S.xG
#?o.
Output
5
通过依次从 (1,1)
(1,1) 移动到 (1,2),(2,2),(1,2),(1,3),(1,4)
(1,2),(2,2),(1,2),(1,3),(1,4)，他可以在五步内到达终点。

样例 2
Input
1 5
So?oG
Output
-1
无论怎么走，都无法到达终点，因此输出 −1
−1。

样例 3
Input
5 5
Sx?x?
o#o#x
?o?o?
x#x#o
?x?oG
Output
10

解题思路

• 网格中的格子类型如下：
• .：空地，可以自由移动。
• #：墙，不可通过。
• S：起点。
• G：终点。
• o：需要特定状态才能通过（状态为 0 时可通过）。
• x：需要特定状态才能通过（状态为 1 时可通过）。
• ?：切换当前状态（0 和 1 之间切换）。
• BFS 需要记录当前位置和当前状态（0 或 1），因为状态会影响某些格子的通行性。

代码分析

变量定义

• a[N][N]：存储网格的二维数组，每个格子用数字表示类型。
• dis[N][N][2]：记录从起点到每个位置 (i,j) 在状态 0 或 1 时的最短步数。
• dx[5] 和 dy[5]：四个方向的移动增量（右、左、下、上）。
• sx, sy：起点坐标。
• ex, ey：终点坐标。

BFS 实现

• 从起点 (sx, sy) 开始，初始状态为 0。每次从队列中取出当前位置和状态，尝试向四个方向移动：
• 如果移动后的位置是空地或终点，直接更新步数。
• 如果移动后的位置是 o 或 x，检查当前状态是否允许通过。
• 如果移动后的位置是 ?，切换状态并更新步数。
• 如果移动后的位置是墙或非法位置，跳过。

输出结果

• 检查终点 (ex, ey) 在状态 0 和 1 时的最短步数，取较小值输出。如果无法到达，输出 -1。
• 代码优化与注意事项
• 使用 0x3f 初始化 dis 数组，表示无穷大。
• 使用 array<int, 3> 存储队列元素（坐标 x, y 和状态 st）。
• 提前剪枝：如果到达终点，跳过后续处理。

复杂度分析

• 时间复杂度：O(n*m)，每个位置和状态最多被访问一次。
• 空间复杂度：O(n*m)，用于存储 dis 数组和队列。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e2+15;
int a[N][N],n,m;
int dis[N][N][2],sx,sy,ex,ey;
int dx[5]={0,0,1,-1};
int dy[5]={1,-1,0,0};
void bfs(int x,int y)
{dis[x][y][0]=0;queue<array<int,3>>q;q.push({x,y,0});while(!q.empty()){array<int,3>j1=q.front();// cout<<j1[0]<<" "<<j1[1]<<'\n';q.pop();if(j1[0]==ex&&j1[1]==ey)continue;for(int i=0;i<=3;i++){array<int,3>jj1;jj1[0]=j1[0]+dx[i];jj1[1]=j1[1]+dy[i];int xx=jj1[0];int yy=jj1[1];if(xx<1||yy<1||xx>n||yy>m)continue;if(a[xx][yy]==0||(j1[2]&&a[xx][yy]==5)||(!j1[2]&&a[xx][yy]==4)||a[xx][yy]==3||a[xx][yy]==2){if(dis[xx][yy][j1[2]]>dis[j1[0]][j1[1]][j1[2]]+1){dis[xx][yy][j1[2]]=dis[j1[0]][j1[1]][j1[2]]+1;q.push({xx,yy,j1[2]});}}else if(a[xx][yy]==6){if(dis[xx][yy][!j1[2]]>dis[j1[0]][j1[1]][j1[2]]+1){dis[xx][yy][!j1[2]]=dis[j1[0]][j1[1]][j1[2]]+1;q.push({xx,yy,!j1[2]});}}}}
}
signed main()
{ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);int sum=0;char c;cin>>n>>m;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){cin>>c;if(c=='.')a[i][j]=0;if(c=='#')a[i][j]=1;if(c=='S')sx=i,sy=j,a[i][j]=2;if(c=='G')ex=i,ey=j,a[i][j]=3;if(c=='o')a[i][j]=4;if(c=='x')a[i][j]=5;if(c=='?')a[i][j]=6;}memset(dis,0x3f,sizeof(dis));bfs(sx,sy);if(min(dis[ex][ey][0],dis[ex][ey][1])==4557430888798830399)cout<<"-1";elsecout<<min(dis[ex][ey][0],dis[ex][ey][1]);return 0;
}