【dfs/bfs】1020.飞地的数量

题目

给你一个大小为 m x n 的二进制矩阵 grid &＃xff0c;其中 0 表示一个海洋单元格、1 表示一个陆地单元格。

一次 移动 是指从一个陆地单元格走到另一个相邻&＃xff08;上、下、左、右&＃xff09;的陆地单元格或跨过 grid 的边界。

返回网格中 无法 在任意次数的移动中离开网格边界的陆地单元格的数量。

示例 1&＃xff1a;

输入&＃xff1a;grid &＃61; [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]
输出&＃xff1a;3
解释&＃xff1a;有三个 1 被 0 包围。一个 1 没有被包围&＃xff0c;因为它在边界上。
示例 2&＃xff1a;

输入&＃xff1a;grid &＃61; [[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]
输出&＃xff1a;0
解释&＃xff1a;所有 1 都在边界上或可以到达边界。

提示&＃xff1a;

m &＃61;&＃61; grid.length
n &＃61;&＃61; grid[i].length
1 <&＃61; m, n <&＃61; 500
grid[i][j] 的值为 0 或 1

正解

链接

自解

class Solution {
public:struct point {int i,j;point(int i,int j) : i(i), j(j) {};};int numEnclaves(vector<vector<int>>& grid) { //多源搜索int landamount &＃61; 0;queue<point> buf;for(int i&＃61;0;i<grid.size();i&＃43;&＃43;) {for(int j&＃61;0;j<grid[0].size();j&＃43;&＃43;) {// cout <if(grid[i][j]&＃61;&＃61;1) {if(i &＃61;&＃61; 0 || i &＃61;&＃61; grid.size()-1 || j &＃61;&＃61; 0 || j &＃61;&＃61; grid[0].size() - 1) {buf.push(point(i, j));grid[i][j] &＃61; 0;}else {landamount&＃43;&＃43;;}}}// cout <}
// cout <while(!buf.empty()) {point tmp &＃61; buf.front();buf.pop();if(tmp.i &＃43; 1 < grid.size() && grid[tmp.i&＃43;1][tmp.j] &＃61;&＃61; 1) {buf.push(point(tmp.i &＃43; 1, tmp.j));grid[tmp.i&＃43;1][tmp.j] &＃61; 0;landamount--;}if(tmp.i - 1 >&＃61; 0 && grid[tmp.i-1][tmp.j] &＃61;&＃61; 1) {buf.push(point(tmp.i - 1, tmp.j));grid[tmp.i-1][tmp.j] &＃61; 0;landamount--;}if(tmp.j &＃43; 1 < grid[0].size() && grid[tmp.i][tmp.j &＃43; 1] &＃61;&＃61; 1) {buf.push(point(tmp.i, tmp.j &＃43; 1));grid[tmp.i][tmp.j&＃43; 1] &＃61; 0;landamount--;}if(tmp.j - 1 >&＃61; 0 && grid[tmp.i][tmp.j - 1] &＃61;&＃61; 1) {buf.push(point(tmp.i, tmp.j - 1));grid[tmp.i][tmp.j- 1] &＃61; 0;landamount--;}}// for(int i&＃61;0;i// for(int j&＃61;0;j// cout <// if(grid[i][j]&＃61;&＃61;1) {// landamount&＃43;&＃43;;// }// }// cout <// }return landamount;}
};