1293. 网格中的最短路径

1293. 网格中的最短路径

BFS、分层图、拆点？

struct Node {
  int x, y, rest;
  Node(int _x, int _y, int _rest) : x(_x), y(_y), rest(_rest) {}
};

class Solution {
 public:
  int shortestPath(vector<vector<int>>& grid, int k) {
    int n = grid.size(), m = grid[0].size();
    queue<Node> q;
    k = min(k, m + n);
    int vis[n][m][k + 1];
    memset(vis, 0, sizeof vis);
    vis[0][0][k] = true;
    q.emplace(0, 0, k);
    for (int step = 0; q.size(); step++) {
      int cnt = q.size();
      while (cnt--) {
        Node u = q.front();
        if (u.x == n - 1 && u.y == m - 1) return step;
        q.pop();
        int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
        for (int i = 0; i < 4; i++) {
          int a = u.x + dx[i], b = u.y + dy[i];
          if (a >= 0 && a < n && b >= 0 && b < m) {
            if (!grid[a][b] && !vis[a][b][u.rest]) {
              q.emplace(a, b, u.rest);
              vis[a][b][u.rest] = true;
            } else if (grid[a][b] && u.rest > 0 && !vis[a][b][u.rest - 1]) {
              q.emplace(a, b, u.rest - 1);
              vis[a][b][u.rest - 1] = true;
            }
          }
        }
      }
    }
    return -1;
  }
};