【多源BFS】01 矩阵 / 飞地的数量 / 舆图中的最高点 / 舆图分析 / 腐烂的苹 ...

    ⭐️个人主页：@小羊     ⭐️所属专栏：搜索算法     很荣幸您能阅读我的文章，诚请品评辅导，欢迎欢迎 ~   

  

---

01 矩阵

• 01 矩阵
  

1. class Solution {
2. public:
3.     vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
4.         int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};
5.         int m = mat.size(), n = mat[0].size();
6.         vector<vector<int>> ret(m, vector<int>(n, -1));
7.         queue<pair<int, int>> q;
8.         for (int i = 0; i < m; i++)
9.             for (int j = 0; j < n; j++)
10.                 if (mat[i][j] == 0)
11.                 {
12.                     q.push({i, j});
13.                     ret[i][j] = 0;
14.                 }
15.         while (q.size())
16.         {
17.             auto [a, b] = q.front();
18.             q.pop();
19.             for (int i = 0; i < 4; i++)
20.             {
21.                 int x = a + dx[i], y = b + dy[i];
22.                 if (x >= 0 && x < m && y >= 0 && y < n && ret[x][y] == -1)
23.                 {
24.                     ret[x][y] = ret[a][b] + 1;
25.                     q.push({x, y});
26.                 }
27.             }
28.         }
29.         return ret;
30.     }
31. };

复制代码

---

飞地的数量

• 飞地的数量
  

1. class Solution {
2. public:
3.     int numEnclaves(vector<vector<int>>& grid) {
4.         int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};
5.         int m = grid.size(), n = grid[0].size();
6.         queue<pair<int, int>> q;
7.         bool used[501][501] = {};
8.         for (int i = 0; i < m; i++)
9.             for (int j = 0; j < n; j++)
10.                 if (i == 0 || i == m - 1 || j == 0 || j == n - 1)
11.                     if (grid[i][j] == 1)
12.                     {
13.                         q.push({i, j});
14.                         used[i][j] = true;
15.                     }
16.         while (q.size())
17.         {
18.             auto [a, b] = q.front();
19.             q.pop();
20.             for (int i = 0; i < 4; i++)
21.             {
22.                 int x = a + dx[i], y = b + dy[i];
23.                 if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] && !used[x][y])
24.                 {
25.                     used[x][y] = true;
26.                     q.push({x, y});
27.                 }
28.             }
29.         }
30.         int ret = 0;
31.         for (int i = 0; i < m; i++)
32.             for (int j = 0; j < n; j++)
33.                 if (grid[i][j] && !used[i][j])
34.                     ret++;
35.         return ret;
36.     }
37. };

复制代码

---

舆图中的最高点

• 舆图中的最高点
  

1. class Solution {
2. public:
3.     vector<vector<int>> highestPeak(vector<vector<int>>& isWater) {
4.         int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};
5.         int m = isWater.size(), n = isWater[0].size();
6.         queue<pair<int, int>> q;
7.         vector<vector<int>> ret(m, vector<int>(n, -1));
8.         for (int i = 0; i < m; i++)
9.             for (int j = 0; j < n; j++)
10.                 if (isWater[i][j] == 1)
11.                 {
12.                     q.push({i, j});
13.                     ret[i][j] = 0;
14.                 }
15.         while (q.size())
16.         {
17.             auto [a, b] = q.front();
18.             q.pop();
19.             for (int i = 0; i < 4; i++)
20.             {
21.                 int x = a + dx[i], y = b + dy[i];
22.                 if (x >= 0 && x < m && y >= 0 && y < n && ret[x][y] == -1)
23.                 {
24.                     ret[x][y] = ret[a][b] + 1;
25.                     q.push({x, y});
26.                 }
27.             }
28.         }
29.         return ret;
30.     }
31. };

复制代码

---

舆图分析

• 舆图分析
  

1. class Solution {
2. public:
3.     int maxDistance(vector<vector<int>>& grid) {
4.         int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};
5.         int n = grid.size();
6.         queue<pair<int, int>> q;
7.         bool used[101][101] = {};
8.         for (int i = 0; i < n; i++)
9.             for (int j = 0; j < n; j++)
10.                 if (grid[i][j] == 1)
11.                     q.push({i, j});
12.         if (q.size() == n * n || q.size() == 0) return -1;
13.         int ret = -1;
14.         while (q.size())
15.         {
16.             ret++;
17.             int sz = q.size();
18.             while (sz--)
19.             {
20.                 auto [a, b] = q.front();
21.                 q.pop();
22.                 for (int i = 0; i < 4; i++)
23.                 {
24.                     int x = a + dx[i], y = b + dy[i];
25.                     if (x >= 0 && x < n && y >= 0 && y < n && !grid[x][y] && !used[x][y])
26.                     {
27.                         used[x][y] = true;
28.                         q.push({x, y});
29.                     }
30.                 }
31.             }
32.         }
33.         return ret;
34.     }
35. };

复制代码

---

腐烂的苹果

• 腐烂的苹果
  

1. class Solution {
2. public:
3.     int rotApple(vector<vector<int> >& grid) {
4.         int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};
5.         int m = grid.size(), n = grid[0].size();
6.         queue<pair<int, int>> q;
7.         for (int i = 0; i < m; i++)
8.             for (int j = 0; j < n; j++)
9.                 if (grid[i][j] == 2)
10.                     q.push({i, j});
11.         int min = -1;
12.         while (q.size())
13.         {
14.             min++;
15.             int sz = q.size();
16.             while (sz--)
17.             {
18.                 auto [a, b] = q.front();
19.                 q.pop();
20.                 for (int k = 0; k < 4; k++)
21.                 {
22.                     int x = a + dx[k], y = b + dy[k];
23.                     if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1)
24.                     {
25.                         grid[x][y] = 2;
26.                         q.push({x, y});
27.                     }
28.                 }
29.             }
30.         }
31.         for (int i = 0; i < m; i++)
32.             for (int j = 0; j < n; j++)
33.                 if (grid[i][j] == 1)
34.                     return -1;
35.         return min;
36.     }
37. };

复制代码

---

本篇文章的分享就到这里了，如果您觉得在本文有所收获，还请留下您的三连支持哦~
   

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。