题是指什么时候你能从左上角游到右下角。第t分钟的时候,水的高度是t。grid[i][j]是海拔,只有当前水的高度没过海拔,我才能游。你可以往四个方向游泳。求问,最少第几分钟我能从左上角游到右下角(有一条路径)
从本质上是要求找到一个最小的h,使得从左上角走到右下角能游完
解题思路:二分答案,h的范围肯定是grid[0][0],到grid中的最大值,取定一个h,看能不能游完
bfs求解
class Solution {
public:
int swimInWater(vector<vector<int>>& grid) {
int m = grid.size();
int n = grid[0].size();
int l = 0, r = 0;
for(int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
r = max(r, grid[i][j]);
}
}
while (l < r) {
int mid = l + (r - l) / 2;
if(bfs(mid, grid)) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
}
using PII = pair<int, int>;
bool bfs(int h, vector<vector<int>>& grid) {
int m = grid.size();
int n = grid[0].size();
queue<PII> q;
int dk[] = {-1, 0, 1, 0, -1};
if(grid[0][0] > h) {
return false;
}
q.push({0,0});
vector<vector<int>> vis(m, vector<int>(n, 0));
vis[0][0] = true;
while(q.size()) {
auto node = q.front();
q.pop();
int x = node.first;
int y = node.second;
if(x == m - 1 && y == n - 1) {
return true;
}
for(int i = 0; i < 4; i++) {
int nx = x + dk[i];
int ny = y + dk[i+1];
if(nx >= 0 && nx < m && ny >= 0 && ny < n && !vis[nx][ny] && grid[nx][ny] <= h) {
vis[nx][ny] = true;
q.push({nx, ny});
}
}
}
return false;
}
};
dfs求解
class Solution {
public:
int swimInWater(vector<vector<int>>& grid) {
int m = grid.size();
int n = grid[0].size();
int l = 0, r = 0;
for(int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
r = max(r, grid[i][j]);
}
}
while (l < r) {
int mid = l + (r - l) / 2;
vector<vector<int>> vis(m, vector<int>(n, 0));
if(dfs(0, 0, mid, vis, grid)) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
}
bool dfs(int x, int y, int h, vector<vector<int>>& vis, vector<vector<int>>& grid) {
int m = grid.size();
int n = grid[0].size();
if(grid[x][y] > h) {
return false;
}
if(x == m - 1 && y == n - 1) {
return true;
}
vis[x][y] = 1;
int dk[] = {-1, 0, 1, 0, -1};
for(int i = 0; i < 4; i++) {
int dx = x + dk[i];
int dy = y + dk[i+1];
if(dx >= 0 && dx < m && dy >= 0 && dy < n && !vis[dx][dy] && dfs(dx, dy, h, vis, grid)) {
return true;
}
}
return false;
}
};
算法复杂度O(mnlog(mn)), 空间复杂度O(mn)