【多源BFS】01 矩阵 / 飞地的数量 / 舆图中的最高点 / 舆图分析 / 腐烂的苹果
https://i-blog.csdnimg.cn/direct/621057c10592434099cf0e6395de3624.png ⭐️个人主页：@小羊 ⭐️所属专栏：搜索算法 很荣幸您能阅读我的文章，诚请品评辅导，欢迎欢迎 ~ https://img-blog.csdnimg.cn/direct/e678d5c05144448f9c9233bf292616a1.gif01 矩阵
[*]01 矩阵
https://i-blog.csdnimg.cn/direct/641ce787466d45f1a8e8021a23d48c36.png
class Solution {
public:
vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
int dx = {1, -1, 0, 0}, dy = {0, 0, 1, -1};
int m = mat.size(), n = mat.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 == 0)
{
q.push({i, j});
ret = 0;
}
while (q.size())
{
auto = q.front();
q.pop();
for (int i = 0; i < 4; i++)
{
int x = a + dx, y = b + dy;
if (x >= 0 && x < m && y >= 0 && y < n && ret == -1)
{
ret = ret + 1;
q.push({x, y});
}
}
}
return ret;
}
};
飞地的数量
[*]飞地的数量
https://i-blog.csdnimg.cn/direct/1f854d8fcbcb482da4d1822b75160416.png
class Solution {
public:
int numEnclaves(vector<vector<int>>& grid) {
int dx = {1, -1, 0, 0}, dy = {0, 0, 1, -1};
int m = grid.size(), n = grid.size();
queue<pair<int, int>> q;
bool used = {};
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 == 1)
{
q.push({i, j});
used = true;
}
while (q.size())
{
auto = q.front();
q.pop();
for (int i = 0; i < 4; i++)
{
int x = a + dx, y = b + dy;
if (x >= 0 && x < m && y >= 0 && y < n && grid && !used)
{
used = true;
q.push({x, y});
}
}
}
int ret = 0;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (grid && !used)
ret++;
return ret;
}
};
舆图中的最高点
[*]舆图中的最高点
https://i-blog.csdnimg.cn/direct/491a28662e3947478e5976868c1e0e03.png
class Solution {
public:
vector<vector<int>> highestPeak(vector<vector<int>>& isWater) {
int dx = {1, -1, 0, 0}, dy = {0, 0, 1, -1};
int m = isWater.size(), n = isWater.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 == 1)
{
q.push({i, j});
ret = 0;
}
while (q.size())
{
auto = q.front();
q.pop();
for (int i = 0; i < 4; i++)
{
int x = a + dx, y = b + dy;
if (x >= 0 && x < m && y >= 0 && y < n && ret == -1)
{
ret = ret + 1;
q.push({x, y});
}
}
}
return ret;
}
};
舆图分析
[*]舆图分析
https://i-blog.csdnimg.cn/direct/c6fb740d12ff4548934cdde5adfc48cc.png
class Solution {
public:
int maxDistance(vector<vector<int>>& grid) {
int dx = {1, -1, 0, 0}, dy = {0, 0, 1, -1};
int n = grid.size();
queue<pair<int, int>> q;
bool used = {};
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (grid == 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 = q.front();
q.pop();
for (int i = 0; i < 4; i++)
{
int x = a + dx, y = b + dy;
if (x >= 0 && x < n && y >= 0 && y < n && !grid && !used)
{
used = true;
q.push({x, y});
}
}
}
}
return ret;
}
};
腐烂的苹果
[*]腐烂的苹果
https://i-blog.csdnimg.cn/direct/23dad656497347a8be918a97e119b58b.png
class Solution {
public:
int rotApple(vector<vector<int> >& grid) {
int dx = {1, -1, 0, 0}, dy = {0, 0, 1, -1};
int m = grid.size(), n = grid.size();
queue<pair<int, int>> q;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (grid == 2)
q.push({i, j});
int min = -1;
while (q.size())
{
min++;
int sz = q.size();
while (sz--)
{
auto = q.front();
q.pop();
for (int k = 0; k < 4; k++)
{
int x = a + dx, y = b + dy;
if (x >= 0 && x < m && y >= 0 && y < n && grid == 1)
{
grid = 2;
q.push({x, y});
}
}
}
}
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (grid == 1)
return -1;
return min;
}
};
本篇文章的分享就到这里了，如果您觉得在本文有所收获，还请留下您的三连支持哦~
https://img-blog.csdnimg.cn/img_convert/ef07608f8c5523995a3671f982ca95bd.jpeg
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]