搜索算法 之 Max Area of island (JAVA版) 一切皆可搜索

1.Max Area of island

题目描述：

给定一个二维的 0-1 矩阵，其中 0 表示海洋，1 表示陆地。单独的或相邻的陆地可以形成岛屿，每个格子只与其上下左右四个格子相邻。求最大的岛屿面积。

输入是一个二维数组，输出是一个整数，表示最大的岛屿面积。

Input:[[1,0,1,1,0,1,0,1],[1,0,1,1,0,1,1,1],[0,0,0,0,0,0,0,1]]Output: 6

思路：利用栈进行深度优先搜索。

1. 遍历二维数组中的所有节点。
2. 用栈对相连的岛进行搜索，记录。
3. 记录最大的岛屿面积

import java.util.Stack;public class MaxIsland {
    public static int[] derection ={
    -1,0,1,0,-1};//相邻两数代表一个方向public static void main(String[] args) {
    int[][] map = {
    {
    1,0,1,1,0,1,0,1},{
    1,0,1,1,0,1,1,1},{
    0,0,0,0,0,0,0,1}};System.out.println(maxAreaOfIsland(map));}public static int maxAreaOfIsland(int[][] map){
    int maxArea = 0,area;int m = map.length; //行数int n = map[0].length; // 列数Stack<Point> stack = new Stack<>();for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
    if (map[i][j] == 1){
    map[i][j] = 0; // 访问过的节点置为0area = 1;stack.push(new Point(i,j));while (!stack.isEmpty()){
    Point top = stack.pop();int r = top.x;int c = top.y;//沿出栈岛的左、上、右、下的方向进行搜索for (int k = 0; k < 4; k++) {
    int newr = r + derection[k];int newc = c + derection[k+1];if(   newr >= 0 && newc >= 0 && newr < m && newc < n 		   														   && map[newr][newc] == 1){
    map[newr][newc] = 0;area++;stack.push(new Point(newr,newc));}}//记录最大的岛屿maxArea = Math.max(area,maxArea);}}}}return maxArea;}
}
class Point{
     //记录二维数组中元素的下标。int x;int y;public Point(int x,int y){
    this.x = x;this.y = y;}
}