本文共 4457 字，大约阅读时间需要 14 分钟。

领扣LintCode算法问题答案-1080. 最大的岛

1080. 最大的岛

描述

给定一个由0和1组成的非空二维数组grid，一个岛由一组四联通（上下左右四方向）的1（表示陆地）组成。假定grid的四周都是水。

返回最大的岛。（没有岛则返回0）

• grid中的每一维度长度都不超过50。

样例 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！因为是4方向联通。

样例 2：

输入：[[0,0,0,0,0,0,0,0]]输出：0

题解

public class Solution {
       /**     * @param grid: a 2D array     * @return: the maximum area of an island in the given 2D array     */    public int maxAreaOfIsland(int[][] grid) {
           // Write your code here        if (grid == null) {
               return 0;        }        int maxR = grid.length;        if (maxR == 0) {
               return 0;        }        int maxC = grid[0].length;        if (maxC == 0) {
               return 0;        }        Queue
   
     pointQueue = new LinkedList<>();        Set
    
      visitedPoint = new HashSet<>();        int maxCount = 0;        for (int r = 0; r < maxR; r++) {
               for (int c = 0; c < maxC; c++) {
                   if (grid[r][c] == 1) {
                       Point p = new Point(r, c);                    if (!visitedPoint.contains(p)) {
                           visitedPoint.add(p);                        pointQueue.offer(p);                        int count = 0;                        while (!pointQueue.isEmpty()) {
                               p = pointQueue.poll();                            count++;                            if (p.r > 0) {
                                   Point tp = new Point(p.r - 1, p.c);                                if (grid[tp.r][tp.c] == 1) {
                                       if (!visitedPoint.contains(tp)) {
                                           visitedPoint.add(tp);                                        pointQueue.offer(tp);                                    }                                }                            }                            if (p.c > 0) {
                                   Point tp = new Point(p.r, p.c - 1);                                if (grid[tp.r][tp.c] == 1) {
                                       if (!visitedPoint.contains(tp)) {
                                           visitedPoint.add(tp);                                        pointQueue.offer(tp);                                    }                                }                            }                            if (p.r + 1 < maxR) {
                                   Point tp = new Point(p.r + 1, p.c);                                if (grid[tp.r][tp.c] == 1) {
                                       if (!visitedPoint.contains(tp)) {
                                           visitedPoint.add(tp);                                        pointQueue.offer(tp);                                    }                                }                            }                            if (p.c + 1 < maxC) {
                                   Point tp = new Point(p.r, p.c + 1);                                if (grid[tp.r][tp.c] == 1) {
                                       if (!visitedPoint.contains(tp)) {
                                           visitedPoint.add(tp);                                        pointQueue.offer(tp);                                    }                                }                            }                        }                        if (count > maxCount) {
                               maxCount = count;                        }                    }                }            }        }        return maxCount;    }         class Point {
           private final int r;        private final int c;        public Point(int r, int c) {
               this.r = r;            this.c = c;        }        public int getR() {
               return r;        }        public int getC() {
               return c;        }        @Override        public boolean equals(Object o) {
               if (this == o)                return true;            if (o == null || getClass() != o.getClass())                return false;            Point point = (Point) o;            return r == point.r && c == point.c;        }        @Override        public int hashCode() {
               return Objects.hash(r, c);        }    }}
    
   

鸣谢

非常感谢你愿意花时间阅读本文章，本人水平有限，如果有什么说的不对的地方，请指正。

欢迎各位留言讨论，希望小伙伴们都能每天进步一点点。

转载地址：https://le-yi.blog.csdn.net/article/details/108809339 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！