LeetCode 1020. 飞地的数量（图的BFS/DFS）

Michael阿明

发布于 2020-07-13 16:33:02

4530

发布于 2020-07-13 16:33:02

文章被收录于专栏：Michael阿明学习之路Michael阿明学习之路

1. 题目

给出一个二维数组 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

利用队列bfs，bool 变量记录是否接触边界
接触，bfs返回0，不接触，返回陆地数量

class Solution {
	vector<vector<int>> dir = {{1,0},{0,1},{0,-1},{-1,0}};
	int m, n, x, y, k;
	int count;
	bool out;
	queue<pair<int,int>> q;
	pair<int,int> tp;
public:
    int numEnclaves(vector<vector<int>>& 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(vector<vector<int>>& A, int i, int j) 
    {
    	count = 0;
    	A[i][j] = 0;//访问过了
    	count++;//陆地计数+1
    	q.push({i,j});
    	bool out = (i==0||i==m-1||j==0||j==n-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(x>=0 && x<m && y>=0 && y<n && A[x][y]==1)
    			{
    				A[x][y] = 0;
    				count++;
    				q.push({x,y});
    				if(!out && (x==0||x==m-1||y==0||y==n-1))
    					out = true;
    			}
    		}
    	}
    	if(out)
    		return 0;
    	return count;
    }
};

2.2 DFS

class Solution {
	vector<vector<int>> dir = {{1,0},{0,1},{0,-1},{-1,0}};
	int m, n;
public:
    int numEnclaves(vector<vector<int>>& 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 = (i==0||i==m-1||j==0||j==n-1);
        			land += dfs(A,i,j,out);
        		}
        	}
        }
        return land;
    }

    int dfs(vector<vector<int>>& A, int i, int j, bool& out) 
    {
    	int x, y, k, count = 0;
    	A[i][j] = 0;//访问过了
    	count++;//陆地计数+1
		for(k = 0; k < 4; ++k)
		{
			x = i + dir[k][0];
			y = j + dir[k][1];
			if(x>=0 && x<m && y>=0 && y<n && A[x][y]==1)
			{
				A[x][y] = 0;
				if(!out && (x==0||x==m-1||y==0||y==n-1))
					out = true;
				count += dfs(A,x,y,out);
			}
		}
    	if(out)
    		return 0;
    	return count;
    }
};