Re: [閒聊] 每日leetcode
1368. Minimum Cost to Make at Least One Valid Path in a Grid
## 思路
0/1 BFS
用deque 存index跟目前的cost
如果箭頭方向一致就加到queue前面, 不同就cost+1加到queue後面
## CODE
```CPP
class Solution {
public:
int minCost(vector<vector<int>>& grid) {
int lenR = grid.size(), lenC = grid[0].size();
vector<pair<int, int>> dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
vector<vector<bool>> seen(lenR, vector<bool>(lenC, false));
deque<tuple<int, int, int>> dequeue;
dequeue.push_front({0, 0, 0});
int res = INT_MAX;
while (!dequeue.empty()) {
auto [r, c, cost] = dequeue.front();
dequeue.pop_front();
if (r == lenR-1 && c == lenC-1) {
return cost;
}
if (seen[r][c]) {
continue;
}
seen[r][c] = 1;
for (int i=0; i<4; ++i) {
int nextR=r+dirs[i].first, nextC=c+dirs[i].second;
if (nextR < 0 || nextR == lenR || nextC < 0 || nextC == lenC
||
seen[nextR][nextC]) {
continue;
}
if (grid[r][c] == i+1) {
dequeue.push_front({nextR, nextC, cost});
} else {
dequeue.push_back({nextR, nextC, cost+1});
}
}
}
return -1;
}
};
```
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 156.146.35.118 (日本)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1737176537.A.78C.html
討論串 (同標題文章)
完整討論串 (本文為第 1292 之 1553 篇)：