题解：AT_abc420_d [ABC420D] Toggle Maze

# 题面翻译：

#### 问题陈述

有一个网格，网格中有 $H$ 行和 $W$ 列。让 $(i,j)$ 表示从上往下第 $i$ 行，从左往上第 $j$ 列的单元格。每个单元格的状态用字符 $A_{i,j}$ 表示，其含义如下：

- `.` ：空单元格。
- `#` : 障碍单元格。
- `S` ：起始单元格。
- `G` : 目标单元格。
- `o` : 打开的单元格。
- `x` : 关闭的单元格。
- `?` : 开关单元。

高桥可以通过一次操作从当前单元格移动到既不是障碍物单元格也不是封闭门单元格的相邻单元格（上、下、左、右）。

此外，每当他移动到一个开关单元时，所有打开的门单元都会变成关闭的门单元，而所有关闭的门单元都会变成打开的门单元。

确定他是否能从位于起始格的初始状态移动到位于目标格的初始状态，如果可能，找出所需的最少操作次数。

# 思路：

问题分析：网格包含多种单元格类型，其中开关在踩踏时会切换所有门的状态。这导致网格的状态（门是开还是闭）会随着开关的触发而改变。所以，我们需要在探索路径时跟踪当前的门状态。

注意到：每次触发开关都会改变门的状态，所以整个网格的门状态会在两种状态之间切换：初始状态（状态 $0$ ）和切换后的状态（状态 $1$ ）。由于每次触发开关都会切换状态，实际上只有两种全局状态需要考虑。

这里我使用的是 $bfs$。

状态定义：使用状态 $(i,j,s)$ 表示在位置 $(i,j)$ 且当前全局门状态为 $s$ 的情况。这样，整个问题可以建模为一个状态空间为 $2hw$ 的图。

每个状态 $(i,j,s)$ 可以转移到相邻的单元格，但移动受到当前门状态的限制（例如，在状态 $s$ 下，闭门在 $s=0$ 时是阻塞的，但在 $s=1$ 时是开放的，反之亦然）。

处理开关：当移动到开关单元格时，全局状态 $s$ 会切换到 $1-s$。其他单元格始终阻塞，而开门和闭门的状态取决于当前 $s$。

具体实现使用一个三维数组 $dis[i][j][s]$ 来记录到达 $(i,j)$ 且状态为 $s$ 的最小步数。初始化时，起点的初始状态 $s=0$，步数为 $0$。然后使用 $BFS$ 队列处理每个状态，检查四个方向的移动。如果移动到开关，则切换状态。

结束：当到达目标单元格时，返回当前步数。如果BFS完成仍未到达目标，则返回 $-1$。

```cpp
#include <iostream>
#include <queue>
#include <climits>
using namespace std;
int dx[5]={1,-1,0,0};
int dy[5]={0,0,1,-1};
int h,w;
char a[505][505];   
int dis[505][505][2];     
int main() {
    cin>>h>>w;
    int sx,sy,ex,ey;
    for (int i=1; i<=h; i++) {      
        for (int j=1; j<=w; j++) {  
            cin>>a[i][j];
            if (a[i][j]=='S') {
                sx=i;
                sy=j;
            } else if (a[i][j]=='G') {
                ex=i;
                ey=j;
            }
            dis[i][j][0]=1e9;
            dis[i][j][1]=1e9;
        }
    }
    queue<pair<pair<int,int>,int>> q;
    dis[sx][sy][0]=0;
    q.push({{sx,sy},0});
    while (!q.empty()) {
        int i=q.front().first.first;
        int j=q.front().first.second;
        int s=q.front().second;
        q.pop();
        int d=dis[i][j][s];
        if (i==ex && j==ey) {
            cout<<d;
            return 0;
        }
        for (int dir=0; dir < 4; dir++) {
            int ni=i+dx[dir];
            int nj=j+dy[dir];
            if (ni < 1 || ni > h || nj < 1 || nj > w) continue;
            char c=a[ni][nj];
            if (c=='#') continue;
            int ns=s;
            if (c=='o' || c=='x') {
                if ((c=='o' && s==0) || (c=='x' && s==1)) {

} else {
                    continue;
                }
            }
            if (c=='?') {
                ns=1 - s;
            }
            if (dis[ni][nj][ns] > d+1) {
                dis[ni][nj][ns]=d+1;
                q.push({{ni,nj},ns});
            }
        }
    }
    cout<<-1;
    return 0;
}
```

正在渲染内容...