695. 岛屿的最大面积
题目
给定一个包含了一些 0 和 1的非空二维数组 grid , 一个 岛屿 是由四个方向 (水平或垂直) 的 1 (代表土地) 构成的组合。你可以假设二维矩阵的四个边缘都被水包围着。
找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为0。)
题解
- dfs/bfs.
- 这题dfs简练一点。
- 注意是先判边界再判点为1，否则可能造成数组越界。
相关
- dfs用递归，bfs用队列。
- bfs中注意计数和置已访问的点为0是入队时做，否则会出现同一层两个点都可达一个有效点，那么这个有效点将入队两次，造成重复。
代码（dfs）
class Solution {
public int maxAreaOfIsland(int[][] grid) {
int maxArea=0;
if(grid==null){
return 0;
}
for(int i=0;i<grid.length;++i){
for(int j=0;j<grid[0].length;++j){
if(grid[i][j]==1){
int area=dfs(grid,i,j);
maxArea=area>maxArea?area:maxArea;
}
}
}
return maxArea;
}
public int dfs(int[][] grid,int i,int j){
int area=1;
grid[i][j]=0;
int[] dx={0,0,-1,1};
int[] dy={-1,1,0,0};
for(int m=0;m<4;++m){
if(vaild(grid,i+dx[m],j+dy[m])&&grid[i+dx[m]][j+dy[m]]==1){
area+=dfs(grid,i+dx[m],j+dy[m]);
}
}
return area;
}
public boolean vaild(int[][] grid,int i,int j){
return i>=0&&i<grid.length&&j>=0&&j<grid[0].length;
}
}
代码(bfs)
class Solution {
public int maxAreaOfIsland(int[][] grid) {
int maxArea=0;
if(grid==null){
return 0;
}
for(int i=0;i<grid.length;++i){
for(int j=0;j<grid[0].length;++j){
if(grid[i][j]==1){
int area=bfs(grid,i,j);
maxArea=area>maxArea?area:maxArea;
}
}
}
return maxArea;
}
private int bfs(int[][] grid,int i,int j){
Queue<Integer> xQue=new LinkedList<Integer>();
Queue<Integer> yQue=new LinkedList<Integer>();
int[] dx={-1,1,0,0};
int[] dy={0,0,-1,1};
int area=0;
xQue.offer(i);
yQue.offer(j);
grid[i][j]=0;//
++area;//
while(!xQue.isEmpty()){
int x=xQue.poll();
int y=yQue.poll();
for(int t=0;t<4;++t){
if(vaild(grid,x+dx[t],y+dy[t])&&grid[x+dx[t]][y+dy[t]]==1){//
xQue.offer(x+dx[t]);
yQue.offer(y+dy[t]);
grid[x+dx[t]][y+dy[t]]=0;//
++area;//
}
}
}
return area;
}
private boolean vaild(int[][] grid,int i,int j){
return i>=0&&i<grid.length&&j>=0&&j<grid[0].length;
}
}
200. 岛屿数量
题目
给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。
示例 1:
输入:
11110
11010
11000
00000
输出: 1
示例 2:
输入:
11000
11000
00100
00011
输出: 3
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/number-of-islands
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题解
DFS
todo
BFS/并查集
代码
class Solution {
public static void main(String[] args) {
char[][] lands = { { '1', '1' }, { '0', '0' }, { '1', '1' } };
int landCnt = numIslands(lands);
System.out.println(landCnt);
}
public static int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}
int landCnt = 0;
for (int i = 0; i < grid.length; ++i) {
for (int j = 0; j < grid[0].length; ++j) {
if (grid[i][j] == '1') {
dfs(grid, i, j);
landCnt++;
}
}
}
return landCnt;
}
private static void dfs(char[][] grid, int i, int j) {
grid[i][j] = '0';
int[] dx = { 0, 0, -1, 1 };
int[] dy = { -1, 1, 0, 0 };
for (int k = 0; k < 4; ++k) {
if (isVaild(grid, i + dx[k], j + dy[k])) {
dfs(grid, i + dx[k], j + dy[k]);
}
}
}
private static boolean isVaild(char[][] grid, int i, int j) {
return i >= 0 && j >= 0 && i < grid.length && j < grid[0].length && grid[i][j] == '1';
}
}