01 矩阵
class Solution {
public:
vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};
int m = mat.size(), n = mat[0].size();
vector<vector<int>> ret(m, vector<int>(n, -1));
queue<pair<int, int>> q;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (mat[i][j] == 0)
{
q.push({i, j});
ret[i][j] = 0;
}
while (q.size())
{
auto [a, b] = q.front();
q.pop();
for (int i = 0; i < 4; i++)
{
int x = a + dx[i], y = b + dy[i];
if (x >= 0 && x < m && y >= 0 && y < n && ret[x][y] == -1)
{
ret[x][y] = ret[a][b] + 1;
q.push({x, y});
}
}
}
return ret;
}
};
飞地的数量
class Solution {
public:
int numEnclaves(vector<vector<int>>& grid) {
int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};
int m = grid.size(), n = grid[0].size();
queue<pair<int, int>> q;
bool used[501][501] = {};
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (i == 0 || i == m - 1 || j == 0 || j == n - 1)
if (grid[i][j] == 1)
{
q.push({i, j});
used[i][j] = true;
}
while (q.size())
{
auto [a, b] = q.front();
q.pop();
for (int i = 0; i < 4; i++)
{
int x = a + dx[i], y = b + dy[i];
if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] && !used[x][y])
{
used[x][y] = true;
q.push({x, y});
}
}
}
int ret = 0;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (grid[i][j] && !used[i][j])
ret++;
return ret;
}
};
地图中的最高点
class Solution {
public:
vector<vector<int>> highestPeak(vector<vector<int>>& isWater) {
int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};
int m = isWater.size(), n = isWater[0].size();
queue<pair<int, int>> q;
vector<vector<int>> ret(m, vector<int>(n, -1));
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (isWater[i][j] == 1)
{
q.push({i, j});
ret[i][j] = 0;
}
while (q.size())
{
auto [a, b] = q.front();
q.pop();
for (int i = 0; i < 4; i++)
{
int x = a + dx[i], y = b + dy[i];
if (x >= 0 && x < m && y >= 0 && y < n && ret[x][y] == -1)
{
ret[x][y] = ret[a][b] + 1;
q.push({x, y});
}
}
}
return ret;
}
};
地图分析
class Solution {
public:
int maxDistance(vector<vector<int>>& grid) {
int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};
int n = grid.size();
queue<pair<int, int>> q;
bool used[101][101] = {};
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (grid[i][j] == 1)
q.push({i, j});
if (q.size() == n * n || q.size() == 0) return -1;
int ret = -1;
while (q.size())
{
ret++;
int sz = q.size();
while (sz--)
{
auto [a, b] = q.front();
q.pop();
for (int i = 0; i < 4; i++)
{
int x = a + dx[i], y = b + dy[i];
if (x >= 0 && x < n && y >= 0 && y < n && !grid[x][y] && !used[x][y])
{
used[x][y] = true;
q.push({x, y});
}
}
}
}
return ret;
}
};
腐烂的苹果
class Solution {
public:
int rotApple(vector<vector<int> >& grid) {
int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};
int m = grid.size(), n = grid[0].size();
queue<pair<int, int>> q;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (grid[i][j] == 2)
q.push({i, j});
int min = -1;
while (q.size())
{
min++;
int sz = q.size();
while (sz--)
{
auto [a, b] = q.front();
q.pop();
for (int k = 0; k < 4; k++)
{
int x = a + dx[k], y = b + dy[k];
if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1)
{
grid[x][y] = 2;
q.push({x, y});
}
}
}
}
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (grid[i][j] == 1)
return -1;
return min;
}
};
本篇文章的分享就到这里了，如果您觉得在本文有所收获，还请留下您的三连支持哦~
