leetcode 695. 岛屿的最大面积

大耗子 2021年02月19日 17次浏览

题目:695. 岛屿的最大面积

695. 岛屿的最大面积

给定一个包含了一些 01 的非空二维数组 grid

一个 岛屿 是由一些相邻的 1 (代表土地) 构成的组合,这里的「相邻」要求两个 1 必须在水平或者竖直方向上相邻。你可以假设 grid 的四个边缘都被 0(代表水)包围着。

找到给定的二维数组中最大的岛屿面积。(如果没有岛屿,则返回面积为 0 。)

示例 1:

[[0,0,1,0,0,0,0,1,0,0,0,0,0],
 [0,0,0,0,0,0,0,1,1,1,0,0,0],
 [0,1,1,0,1,0,0,0,0,0,0,0,0],
 [0,1,0,0,1,1,0,0,1,0,1,0,0],
 [0,1,0,0,1,1,0,0,1,1,1,0,0],
 [0,0,0,0,0,0,0,0,0,0,1,0,0],
 [0,0,0,0,0,0,0,1,1,1,0,0,0],
 [0,0,0,0,0,0,0,1,1,0,0,0,0]]

对于上面这个给定矩阵应返回 6。注意答案不应该是 11 ,因为岛屿只能包含水平或垂直的四个方向的 1

示例 2:

[[0,0,0,0,0,0,0,0]]

对于上面这个给定的矩阵, 返回 0

注意: 给定的矩阵grid 的长度和宽度都不超过 50。

解题思路

使用递归的方式,执行深度寻路,路过的地方就标记为0。

  1. 从上到下,从左到右找到第一个岛屿的位置,然后对岛屿进行深度搜索,比较该岛屿是否为最大岛屿。
  2. 搜索路径全部标记为0,代表抹去岛屿,同时岛屿面积+1。
  3. 重复第一第二步骤。

代码

int directions[4][2] = { {0,1}, {1,0}, {0,-1},{-1,0} };

class Solution {
public:
	int maxAreaOfIsland(vector<vector<int>>& grid) {
		if (grid.size() == 0 || grid[0].size() == 0) return 0;
		int maxarea = 0;
		int area = 0;
		for (int i = 0; i < grid.size(); i++){
			for (int j = 0; j < grid[i].size(); j++){
				// 找到岛屿,岛屿标记+1,并抹去该岛屿
				if (grid[i][j]) {
					// 获取最大面积
					area = isLandCore(grid, i, j, 0);
					maxarea = area > maxarea ? area : maxarea;
				}
			}
		}

		return maxarea;
	}

	int isLandCore(vector<vector<int>>& grid, int row, int col,int size) {
		// 递归推出条件,1. 超出边界 2. 位置不是岛屿
		if (row >= grid.size() || row < 0 || col >= grid[0].size() || col < 0 || !grid[row][col])
			return size; // 碰到边界,不是岛屿,面积不变
		// 步骤2 路过的路径设置为0 代表抹去岛屿,面积增加
		grid[row][col] = 0;
		size++;
		for (int i = 0; i < 4; i++){
			// 获取其他路径下的面积
			size = isLandCore(grid, row + directions[i][0], col + directions[i][1],size);
		}
		return size;
	}


	int print(vector<vector<int>>& grid) {
		for (int i = 0; i < grid.size(); i++)
		{
			for (int j = 0; j < grid[i].size(); j++)
			{
				cout << grid[i][j] << "  " ;
			}
			cout << endl;
		}
		cout << endl;
		return 0;
	}
};

int main()
{
	vector<vector<int>> gird = { {0,0,1,0,0,0,0,1,0,0,0,0,0},
				{0,0,0,0,0,0,0,1,1,1,0,0,0},
				{0,1,1,0,1,0,0,0,0,0,0,0,0},
				{0,1,0,0,1,1,0,0,1,0,1,0,0},
				{0,1,0,0,1,1,0,0,1,1,1,0,0},
				{0,0,0,0,0,0,0,0,0,0,1,0,0},
				{0,0,0,0,0,0,0,1,1,1,0,0,0},
				{0,0,0,0,0,0,0,1,1,0,0,0,0} };

	Solution sln; 
	sln.print(gird);
	int num = sln.maxAreaOfIsland(gird);
	sln.print(gird);

	cout << num << endl;
	return 0;
}