建设网站 法律责任,wordpress 链接扁平化,网页设计师职责,建设银行中国网站首页文章目录1. 题目2. 解题2.1 BFS2.2 DFS1. 题目
给出一个二维数组 A#xff0c;每个单元格为 0#xff08;代表海#xff09;或 1#xff08;代表陆地#xff09;。
移动是指在陆地上从一个地方走到另一个地方#xff08;朝四个方向之一#xff09;或离开网格的边界。 …
文章目录1. 题目2. 解题2.1 BFS2.2 DFS1. 题目
给出一个二维数组 A每个单元格为 0代表海或 1代表陆地。
移动是指在陆地上从一个地方走到另一个地方朝四个方向之一或离开网格的边界。
返回网格中无法在任意次数的移动中离开网格边界的陆地单元格的数量。
示例 1
输入[[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]
输出3
解释
有三个 1 被 0 包围。一个 1 没有被包围因为它在边界上。示例 2
输入[[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]
输出0
解释
所有 1 都在边界上或可以到达边界。提示
1 A.length 500
1 A[i].length 500
0 A[i][j] 1
所有行的大小都相同来源力扣LeetCode 链接https://leetcode-cn.com/problems/number-of-enclaves 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
2. 解题
2.1 BFS
利用队列bfsbool 变量记录是否接触边界接触bfs返回0不接触返回陆地数量
class Solution {vectorvectorint dir {{1,0},{0,1},{0,-1},{-1,0}};int m, n, x, y, k;int count;bool out;queuepairint,int q;pairint,int tp;
public:int numEnclaves(vectorvectorint A) {m A.size(), n A[0].size();int land 0, i, j;for(i 0; i m; i){for(j 0; j n; j){if(A[i][j] 1)//陆地{land bfs(A,i,j);}}}return land;}int bfs(vectorvectorint A, int i, int j) {count 0;A[i][j] 0;//访问过了count;//陆地计数1q.push({i,j});bool out (i0||im-1||j0||jn-1);while(!q.empty()){tp q.front();q.pop();for(k 0; k 4; k){x tp.first dir[k][0];y tp.second dir[k][1];if(x0 xm y0 yn A[x][y]1){A[x][y] 0;count;q.push({x,y});if(!out (x0||xm-1||y0||yn-1))out true;}}}if(out)return 0;return count;}
};2.2 DFS
class Solution {vectorvectorint dir {{1,0},{0,1},{0,-1},{-1,0}};int m, n;
public:int numEnclaves(vectorvectorint A) {m A.size(), n A[0].size();int land 0, i, j;bool out;for(i 0; i m; i){for(j 0; j n; j){if(A[i][j] 1)//陆地{out (i0||im-1||j0||jn-1);land dfs(A,i,j,out);}}}return land;}int dfs(vectorvectorint A, int i, int j, bool out) {int x, y, k, count 0;A[i][j] 0;//访问过了count;//陆地计数1for(k 0; k 4; k){x i dir[k][0];y j dir[k][1];if(x0 xm y0 yn A[x][y]1){A[x][y] 0;if(!out (x0||xm-1||y0||yn-1))out true;count dfs(A,x,y,out);}}if(out)return 0;return count;}
};
