该题可以抽象为从左上角到右上角需要的最小花费, 求最小花费就是求最小路径
其中边权可以抽象为 0 1, 当一个点存在方向时, 权值为 0 没有方向时 权值为 1
01bfs:
? 就是讲能够到达权值为 0 的边加入到双端队列的首部, 不能到达权值的边放到双端队列
的尾部, 这样其实在第一次遍历到 右下角的点时 就是最终答案
至于 vis 数组是否需要加上, 其实不需要加, vis 防止已经判断点继续回溯,
- dis[x][y] + cost <dis[xnxt][ynxt] // 这个判断其实就可以使的即使判断点回溯, 也需要满足权值比先前到达 xnxt,ynext 的路径花费小, 才能够更新, 因此, 这道题其实可以用 普通 queue 直接做出来, 只不过需要遍历更多的路径, 01bfs 这道题很快, 时间复杂度为 o(n)
- const int dx[5] = {0, 0, 0, 1, -1};
- const int dy[5] = {0, 1, -1, 0, 0};
- const int inf = 0x3f3f3f3f;
- typedef pair<int, int> pir;
- class Solution {
- public:
- int minCost(vector<vector<int>>& grid) {
- int n = grid.size(), m = grid[0].size();
- bool vis[n][m];
- int dis[n][m];
- memset(dis, inf, sizeof(dis));
- deque<pir> pq;
- pq.push_front({0, 0});
- dis[0][0] = 0;
- while(!pq.empty()) {
- pir front = pq.front();
- int x = front.first, y = front.second;
- pq.pop_front();
- if(x == n - 1 && y == m - 1) return dis[x][y];
- for(int i = 1; i <= 4; i++) {
- int xnxt = x + dx[i], ynxt = y + dy[i], cost = grid[x][y] == i ? 0 : 1;
- if(xnxt <0 || xnxt>= n || ynxt <0 || ynxt>= m) continue;
- if(dis[x][y] + cost < dis[xnxt][ynxt]) {
- dis[xnxt][ynxt] = dis[x][y] + cost;
- if(cost == 0) pq.push_front({xnxt, ynxt});
- if(cost == 1) pq.push_back({xnxt, ynxt});
- }
- }
- }
- return 0;
- }
- };
来源: http://www.bubuko.com/infodetail-3448549.html