|
You must practice being stupid, dumb, unthinking, empty.
你得学着痴一点，钝一些，少想一些，彻底放空自己。 给定一个包含了一些0和1的非空二维数组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 。 对于上面这个给定的矩阵, 返回 0。 注意: 给定的矩阵grid 的长度和宽度都不超过 50。 这题无论使用DFS还是BFS都很好解决，DFS就是沿着一个方向一直走下去，直到不满足条件为止（要么走出grid的边缘，要么当前位置是0），就像下面这样，
代码如下
1public int maxAreaOfIsland(int[][] grid) {
2 int maxArea = 0;
3 for (int i = 0; i < grid.length; i++)
4 for (int j = 0; j < grid[0].length; j++)
5 if (grid[i][j] == 1) {//如果当前位置是1，开始计算
6 maxArea = Math.max(maxArea, dfs(grid, i, j));
7 }
8 return maxArea;
9}
10
11public int dfs(int[][] grid, int i, int j) {
12 //边界条件的判断
13 if (i >= 0 && i < grid.length && j >= 0 && j < grid[0].length && grid[i][j] == 1) {
14 //当前位置如果是1，为了防止重复计算就把他置为0，然后再从他的上下左右四个方向开始查找
15 grid[i][j] = 0;
16 return 1 + dfs(grid, i + 1, j) + dfs(grid, i - 1, j) + dfs(grid, i, j - 1) + dfs(grid, i, j + 1);
17 }
18 return 0;
19}
BFS我们可以使用一个队列来实现，他的实现原理就是如果一个位置是1，我们就把他上下左右为1的点的坐标全部加入到队列中，然后改变当前位置的坐标为0，防止重复计算。加入队列之后再一个个出队，然后再以出队的那个点重复上面的操作……，直到队列为空为止。就像下面这样，假如遍历到红色的1，我们就把他上下左右为1的位置坐标全部加入到队列中。
1public int maxAreaOfIsland(int[][] grid) {
2 int maxArea = 0;
3 for (int i = 0; i < grid.length; i++)
4 for (int j = 0; j < grid[0].length; j++)
5 if (grid[i][j] == 1) {//如果当前位置是1，开始计算
6 maxArea = Math.max(maxArea, bfs(grid, i, j));
7 }
8 return maxArea;
9}
10
11public int bfs(int[][] grid, int i, int j) {
12 int m = grid.length, n = grid[0].length;
13 if (grid[i][j] == 0)
14 return 0;
15 grid[i][j] = 0;
16 //队列中存储的是个二维数组，这个二维数组就是格子的坐标
17 Queue<int[]> queue = new LinkedList<>();
18 //offer表示添加到队列的末尾
19 queue.offer(new int[]{i, j});
20 //分别表示右，左，下，上，四个方向
21 int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
22 int res = 1;
23 while (!queue.isEmpty()) {
24 //poll表示从队列的头部移除一个元素
25 int[] pos = queue.poll();
26 //然后从pos坐标的4个方向再分别查找
27 for (int[] dir : dirs) {
28 int x = dir[0] + pos[0];
29 int y = dir[1] + pos[1];
30 //边界条件的判断
31 if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] == 0) {
32 continue;
33 }
34 grid[x][y] = 0;
35 res++;
36 queue.offer(new int[]{x, y});
37 }
38 }
39 return res;
40}
如果对图的遍历比较了解的话，这两种方式很容易想到，一个是沿着一个方向一直走下去，一个就像波浪一样，沿着一个点然后往四周一圈一圈的发散。
|
