題目描述
有一個 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;
}