You are given an m x n binary matrix grid. 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.

The area of an island is the number of cells with a value 1 in the island.

Return the maximum area of an island in grid. If there is no island, return 0.

&nbsp;
Example 1:

Input: grid = [[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]]
Output: 6
Explanation: The answer is not 11, because the island must be connected 4-directionally.


Example 2:

Input: grid = [[0,0,0,0,0,0,0,0]]
Output: 0


&nbsp;
Constraints:


	m == grid.length
	n == grid[i].length
	1 &lt;= m, n &lt;= 50
	grid[i][j] is either 0 or 1.


from queue import Queue
from typing import List


class Solution:
    def __init__(self):
        self.directions = [[-1, 0], [0, 1], [1, 0], [0, -1]]

    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        [rows, cols] = [len(grid), len(grid[0])]

        ans = 0
        visited: List[List[bool]] = [[False for _ in range(cols)] for _ in range(rows)]
        
        for i in range(rows):
            for j in range(cols):
                if not visited[i][j] and grid[i][j]:
                    res = self.dfs(grid, visited, i, j)
                    ans = res if res > ans else ans 

        return ans

    def dfs(self, grid: List[List[int]], visited: List[List[bool]], startRow: int, startCol: int) -> int:
        [rows, cols] = [len(grid), len(grid[0])]
        
        fields = 1
        q = Queue()

        q.put([startRow, startCol])
        visited[startRow][startCol] = True

        while not q.empty():
            [row, col] = q.get()
            for d in self.directions:
                newRow = row + d[0]
                newCol = col + d[1]
                if newRow >= 0 and newRow < rows and newCol >= 0 and newCol < cols and not visited[newRow][newCol] and grid[newRow][newCol]:
                    visited[newRow][newCol] = True
                    fields += 1
                    q.put([newRow, newCol])
        
        return fields
class Solution {
    public int maxAreaOfIsland(int[][] grid) {

      final int rows=grid.length;
      final int cols=grid[0].length;
      final int[][] dirrections=new int[][]{{1,0},{0,1},{-1,0},{0,-1}};
      Map<String,List<int[]>> adj=new HashMap<>();
      boolean[][] visited=new boolean[rows][cols];
      Queue<String> queue=new LinkedList<>();
      int res=0;

      for(int i=0;i<grid.length;i++)
      {
        for(int j=0;j<grid[i].length;j++)
        {

          List<int[]> list=new ArrayList<>();
          for(int[] dirrection:dirrections)
          {
            int newRow=dirrection[0]+i;
            int newCol=dirrection[1]+j;

            boolean isInBoard=newRow>=rows||newRow<0||newCol>=cols||newCol<0;
            if(!isInBoard)
            {
              list.add(new int[]{newRow,newCol,grid[newRow][newCol]});
            }
          }

          adj.put(getNodeStringFormat(i,j,grid[i][j]),list);
        }
      }

      for(int i=0;i<rows;i++)
      {
        for(int j=0;j<cols;j++)
        {
          int count=0;
          if(visited[i][j])
            continue;
          queue.add(getNodeStringFormat(i,j,grid[i][j]));
          while(!queue.isEmpty())
          {
            String currentStr=queue.poll();
            String[] current=currentStr.split(",");

            int row=Integer.valueOf(current[0]);
            int col=Integer.valueOf(current[1]);
            int isLand=Integer.valueOf(current[2]);
            if(!adj.containsKey(currentStr))
                continue;
            if(visited[row][col])
                continue;
            if(isLand==1)
                count++;
            visited[row][col]=true;
            for(int[] item:adj.get(currentStr))
            {
              int newRow=item[0];
              int newCol=item[1];
              int newIsLand=item[2];
              if(!visited[newRow][newCol] && newIsLand==1 && isLand==1)
                  queue.add(getNodeStringFormat(newRow,newCol,newIsLand));
            }
          }
          res=Math.max(res,count);
        }
      }

      return res;

    }
  private String getNodeStringFormat(int row,int col,int isLand)
  {
      StringBuilder sb=new StringBuilder();
      sb.append(row);
      sb.append(",");
      sb.append(col);
      sb.append(",");
      sb.append(isLand);
    return sb.toString();
  }
}
class Solution {
public:
    int cal(vector<vector<int>>& grid,int i,int j,int& m,int& n){
        if(i==m || j==n || i<0 || j<0 || grid[i][j]==0)
            return 0;
        grid[i][j]=0;
        return 1+cal(grid,i,j+1,m,n)+cal(grid,i+1,j,m,n)+cal(grid,i,j-1,m,n)+cal(grid,i-1,j,m,n);
    }
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int m=grid.size(),n=grid[0].size(),maxArea=0;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(grid[i][j]==1){
                    int area=0;
                    area=cal(grid,i,j,m,n);
                    maxArea=max(maxArea,area);
                }
            }
        }
        return maxArea;
    }
};
var maxAreaOfIsland = function(grid) {
    let result = 0;
    const M = grid.length;
    const N = grid[0].length;
    const isOutGrid = (m, n) => m < 0 || m >= M || n < 0 || n >= N;
    const island = (m, n) => grid[m][n] === 1;
    const dfs = (m, n) => {
        if (isOutGrid(m, n) || !island(m, n)) return 0;

        grid[m][n] = 'X';
        const top = dfs(m - 1, n);
        const bottom = dfs(m + 1, n);
        const left = dfs(m, n - 1);
        const right = dfs(m, n + 1);
        return 1 + top + bottom + left + right;
    };

    for (let m = 0; m < M; m++) {
        for (let n = 0; n < N; n++) {
            if (!island(m, n)) continue;
            const area = dfs(m, n);

            result = Math.max(area, result);
        }
    }
    return result;
};
Max Area of Island