问题
该文章的最新版本已迁移至个人博客【比特飞】，单击链接 https://www.byteflying.com/archives/3736 访问。
给定一个包含了一些 0 和 1的非空二维数组 grid , 一个 岛屿 是由四个方向 (水平或垂直) 的 1 (代表土地) 构成的组合。你可以假设二维矩阵的四个边缘都被水包围着。
找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为0。)
[[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’。
注：以上紫色部分为该题的解，粉红色部分是要注意的部分，答案是6而不是11。
[[0,0,0,0,0,0,0,0]]
对于上面这个给定的矩阵, 返回 0。
注意: 给定的矩阵grid 的长度和宽度都不超过 50。
Given a non-empty 2D array grid of 0's and 1's, an island is a group of 1's (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.
Find the maximum area of an island in the given 2D array. (If there is no island, the maximum area is 0.)
[[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]]
Given the above grid, return 6. Note the answer is not 11, because the island must be connected 4-directionally.
[[0,0,0,0,0,0,0,0]]
Given the above grid, return 0.
Note: The length of each dimension in the given grid does not exceed 50.
示例
该文章的最新版本已迁移至个人博客【比特飞】，单击链接 https://www.byteflying.com/archives/3736 访问。
public enum SearchType {
DepthFirstSearch,
BreadthFirstSearch
}
public class Program {
public static void Main(string[] args) {
int[,] nums = null;
nums = new int[,]{
{ 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}
};
var res = MaxAreaOfIsland(nums, SearchType.DepthFirstSearch);
Console.WriteLine(res);
nums = new int[,]{
{ 0,0,0,0,0,0,0,0}
};
res = MaxAreaOfIsland(nums, SearchType.BreadthFirstSearch);
Console.WriteLine(res);
Console.ReadKey();
}
private static int MaxAreaOfIsland(int[,] grid, SearchType searchType) {
//记录最大值
var max = 0;
//记录行和列数量
var rows = grid.GetLength(0);
var cols = grid.GetLength(1);
//标记是否已经访问过了
var visited = new bool[rows, cols];
if(searchType == SearchType.DepthFirstSearch) {
//使用深度优先搜索来遍历原数组
for(var i = 0; i < rows; i++) {
for(var j = 0; j < cols; j++) {
if(visited[i, j]) continue;
max = Math.Max(max, DepthFirstSearch(grid, i, j, visited));
}
}
} else {
max = Math.Max(max, BreadthFirstSearch(grid, visited));
}
//返回最大值
return max;
}
private static int DepthFirstSearch(int[,] grid, int i, int j, bool[,] visited) {
//深度优先搜索
//记录行和列数量
var rows = grid.GetLength(0);
var cols = grid.GetLength(1);
//处理边界
if(i >= rows || j >= cols || i < 0 || j < 0) return 0;
//若已经访问或不是岛屿则返回0
if(visited[i, j] || grid[i, j] == 0) return 0;
//标记当前节点已经访问过了
visited[i, j] = true;
//流程到了这里，当前节点为岛屿，所以返回上、下、左、右4个方向的结果+1
return DepthFirstSearch(grid, i + 1, j, visited) +
DepthFirstSearch(grid, i - 1, j, visited) +
DepthFirstSearch(grid, i, j + 1, visited) +
DepthFirstSearch(grid, i, j - 1, visited) + 1;
}
private static int BreadthFirstSearch(int[,] grid, bool[,] visited) {
//广度优先搜索
//记录最大值
var max = 0;
//记录行和列数量
var rows = grid.GetLength(0);
var cols = grid.GetLength(1);
//开始搜索
for(var i = 0; i < rows; i++) {
for(var j = 0; j < cols; j++) {
//若已经访问或不是岛屿则返回0
if(visited[i, j] || grid[i, j] == 0) continue;
//记录临时岛屿面积
var area = 0;
//栈在广度优先中的应用
var stack = new Stack<KeyValuePair<int, int>>();
//将当前节点压入栈中
stack.Push(KeyValuePair.Create(i, j));
//标记当前节点已经访问过了
visited[i, j] = true;
//栈空时，代表当前广度（横向）已搜索完毕
while(stack.Count != 0) {
//临时岛屿+1
area++;
//取出栈顶数据并记录
var curNode = stack.Pop();
//记录刚取出的栈顶元素的索引值
var rowIndex = curNode.Key;
var colIndex = curNode.Value;
//从上、下、左、右4个方向
var fix = new int[4, 2] {
{-1,0 },
{ 1,0},
{ 0,-1},
{ 0,1}
};
for(int k = 0; k < fix.GetLength(0); k++) {
//处理边界
if(rowIndex + fix[k, 0] >= 0 &&
rowIndex + fix[k, 0] < rows &&
colIndex + fix[k, 1] >= 0 &&
colIndex + fix[k, 1] < cols) {
//若为1或没有访问过，则继续
if(grid[rowIndex + fix[k, 0], colIndex + fix[k, 1]] == 1 &&
visited[rowIndex + fix[k, 0], colIndex + fix[k, 1]] == false) {
stack.Push(KeyValuePair.Create(rowIndex + fix[k, 0], colIndex + fix[k, 1]));
visited[rowIndex + fix[k, 0], colIndex + fix[k, 1]] = true;
}
}
}
}
//比较当前最大值
max = Math.Max(max, area);
}
}
//返回最大值
return max;
}
}以上给出2种算法实现，以下是这个案例的输出结果：
该文章的最新版本已迁移至个人博客【比特飞】，单击链接 https://www.byteflying.com/archives/3736 访问。
6
0分析：
显而易见，深度优先搜索和广度优先搜索的时间复杂度均为： 。