01bfs|dq addfirst

lc2290

0-1 BFS，双端队列处理网格移动代价

无障碍（代价0）节点入队首、有障碍（代价1）节点入队尾

求解从网格起点到终点的最小障碍移除数量

喵喵dj版(遇到0就addFirst，优先走短路，0-1BFS通过可插双端队列的队首省了优先队列的排序log，极大地优化了时间复杂度

class Solution {
static constexpr int DIRS[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
public:
int minimumObstacles(vector<vector<int>> &grid) {
int m = grid.size(), n = grid[0].size();
vector<vector<int>> dis(m, vector<int>(n, INT_MAX));
dis[0][0] = 0;
deque<pair<int, int>> q;
q.emplace_front(0, 0);
while (!q.empty()) {
auto [i, j] = q.front();
q.pop_front();
for (auto& [dx, dy] : DIRS) {
int x = i + dx, y = j + dy;
if (0 <= x && x < m && 0 <= y && y < n) {
int g = grid[x][y];
if (dis[i][j] + g < dis[x][y]) {
dis[x][y] = dis[i][j] + g; //update
g == 0 ? q.emplace_front(x, y) : q.emplace_back(x, y);
}
}
}
}
return dis[m - 1][n - 1];
}
};

计算新路径的障碍代价，若新代价更小则更新最短障碍数

最后根据位置是否为障碍，将节点分别插入双端队列的队首（空地）或队尾（障碍），以此实现0-1 BFS的核心逻辑