DAY 14
0
Software Development

## 10.3 幾個簡單的 Leetcode 例題

### Leetcode 1293. Shortest Path in a Grid with Obstacles Elimination

https://leetcode.com/problems/shortest-path-in-a-grid-with-obstacles-elimination/

``````class Solution {
public:
int shortestPath(vector<vector<int>>& grid, int k) {
int m = grid.size();
int n = grid[0].size();
int dist[1605][50][50];
memset(dist, -1, sizeof(dist));

queue<int> Q;
Q.push(0); Q.push(0); Q.push(0); dist[0][0][0] = 0;
while (!Q.empty()) {
int l = Q.front(); Q.pop();
int x = Q.front(); Q.pop();
int y = Q.front(); Q.pop();
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
if (x == m-1 && y == n-1) return dist[l][x][y];
for (int f = 0; f < 4; f++) {
int nx = x + dx[f];
int ny = y + dy[f];
if (nx>=0 && nx<m && ny>=0 && ny<n) {
if (l < k && grid[nx][ny] == 1 && dist[l+1][nx][ny] == -1) {
dist[l+1][nx][ny] = dist[l][x][y] + 1;
Q.push(l+1); Q.push(nx); Q.push(ny);
} else if (grid[nx][ny] == 0 && dist[l][nx][ny] == -1) {
dist[l][nx][ny] = dist[l][x][y] + 1;
Q.push(l); Q.push(nx); Q.push(ny);
}
}
}
}
return -1;
}
};
``````

### Leetcode 1368. Minimum Cost to Make At Least One Valid Path in a Grid

https://leetcode.com/problems/minimum-cost-to-make-at-least-one-valid-path-in-a-grid/

``````class Solution {
public:
int minCost(vector<vector<int>>& grid) {
int m = grid.size();
int n = grid[0].size();
int dist[105][105];
memset(dist, -1, sizeof(dist));
deque<pair<int, int>> Q;
Q.push_back({0, 0});
dist[0][0] = 0;
while (!Q.empty()) {
auto p = Q.front(); Q.pop_front();
int x = p.first;
int y = p.second;
const int dx[4] = {0, 0, 1, -1};
const int dy[4] = {1, -1, 0, 0};
for(int f = 0; f < 4; f++) {
int nx = x + dx[f];
int ny = y + dy[f];
if (nx>=0 && nx<m && ny>=0 && ny<n) {
if (grid[x][y] == f+1 && (dist[nx][ny] == -1 || dist[nx][ny] > dist[x][y])) {
dist[nx][ny] = dist[x][y];
Q.push_front({nx, ny});
} else if (grid[x][y] != f+1 && (dist[nx][ny] == -1 || dist[nx][ny] > dist[x][y] + 1)) {
dist[nx][ny] = dist[x][y] + 1;
Q.push_back({nx, ny});
}
}
}
}

return dist[m-1][n-1];
}
};
``````