迷宫

其实分为两条路径就可以了

1. 一条是直接从起点走到终点
2. 一条是先从起点到钥匙的位置 再从钥匙的位置到终点

如果两条都不存在 就输出-1
只存在一条 就输出这一条
两条都存在 就取小再输出 第一次就WA在这。。
代码如下

#include <bits/stdc++.h>
using namespace std;
string s[505];

int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

int main() {
  ios::sync_with_stdio(0), cin.tie(0);
  int n, m; cin >> n >> m;
  int sx, sy, ex, ey, kx, ky;
  for (int i = 0; i < n; ++i) cin >> s[i];
  vector<vector<vector<int>>> vis(n + 5, vector<vector<int>>(m + 5, vector<int>(2, -1)));
  
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < m; ++j) {
      if (s[i][j] == 'S') sx = i, sy = j;
      if (s[i][j] == 'E') ex = i, ey = j;
      if (s[i][j] == 'K') kx = i, ky = j;
    }

  auto inmp = [&](int x, int y) -> bool {
    return 0 <= x && x < n && 0 <= y && y < m;
  };

  auto bfs = [&](int sx, int sy, int a) -> void {
    queue<pair<int, int>> q;
    q.push({sx, sy});
    vis[sx][sy][a] = 0;
    while (!q.empty()) {
      int x = q.front().first, y = q.front().second;
      q.pop();
      for (int i = 0; i < 4; ++i) {
        int nx = x + dx[i], ny = y + dy[i];
        if (a == 0) {
          if (inmp(nx, ny) && s[nx][ny] != 'W' && s[nx][ny] != 'D' && vis[nx][ny][a] == -1) {
            vis[nx][ny][a] = vis[x][y][a] + 1;
            q.push({nx, ny});
          }
        }
        else {
          if (inmp(nx, ny) && s[nx][ny] != 'W' && vis[nx][ny][a] == -1) {
            vis[nx][ny][a] = vis[x][y][a] + 1;
            q.push({nx, ny});
          }
        }
      }
    }
  };

  bfs(sx, sy, 0);
  //WA的原因是没考虑path1和path2的大小关系
  //如果两条路径都存在确实应该取更小的
  int path1 = vis[ex][ey][0];
  int path2 = -1;

  if (vis[kx][ky][0] != -1) {
    bfs(kx, ky, 1);
    if (vis[ex][ey][1] != -1) {
      path2 = vis[kx][ky][0] + vis[ex][ey][1];
    }
  }

  int ans = -1;
  if (path1 != -1) ans = path1;
  if (path2 != -1) {
    if (ans == -1 || path2 < ans) ans = path2;
  }
  cout << ans << '\n';
  /*
  或者这样去判断 相较上面的更加复杂了 
  故还是分成两条路径加以判断更加方便
  if (vis[ex][ey][0] == -1) {
    if (vis[kx][ky][0] == -1) cout << -1 << '\n';
    else {
      bfs(kx, ky, 1);
      if (vis[ex][ey][1] == -1) cout << -1 << '\n';
      else cout << vis[ex][ey][1] + vis[kx][ky][0] << '\n';
    }
  } 
  else {
    if (vis[kx][ky][0] != -1) {
      bfs(kx, ky, 1);
      if (vis[ex][ey][1] == -1) cout << vis[ex][ey][0] << '\n';
      else cout << min(vis[ex][ey][0], vis[ex][ey][1] + vis[kx][ky][0]) << '\n';
    }
    else cout << vis[ex][ey][0] << '\n';
  }
  */
}