题解：AT_abc420_d [ABC420D] Toggle Maze

· · 题解

有一个 H 行 W 列的网格，每个格子可能是空格（.）、障碍物（#）、起点（S）、终点（G）、开着的门（o）、关着的门（x）或开关（?）。高桥从起点出发，每次能上下左右移到相邻格子，但不能移到障碍物或关着的门。特别地，每踩一次开关，所有门的状态会反转。请判断高桥能否走到终点，能的话求最少移动次数，不能则输出 -1。1≤H,W≤500。

这题一眼就是 BFS。看不出来就多练。
用 dist[state][i][j] 表示在门反转状态为 state 时到达 (i,j) 的最小步数（state=0 表示初始状态，state=1 表示反转后状态）。初始化为 INT_MAX。

从起点开始 BFS，初始状态为 0。 对每个位置，尝试向四个方向移动，计算新位置 (ni, nj) 和新状态 n。若新位置是开关，则状态反转；否则状态不变。
判断移动是否合法，若合法且找到更短路径，则更新距离并加入队列。一旦到达终点，立即输出步数并结束程序。如果 BFS 结束仍未到达终点，则输出 -1，表示无法到达。

时间复杂度为 O(H\times W)，可以通过。
C++通过代码。