695. Max Area of Island

https://leetcode.com/problems/max-area-of-island/

Python

DFS

class Solution:
    def __init__(self):
        self.grid = []
        self.seem = set()
        self.row_limit = 0
        self.col_limit = 0

    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        self.grid = grid
        self.seem = set()
        self.row_limit = len(grid)
        self.col_limit = len(grid[0])

        maximum = 0
        for row in range(self.row_limit):
            for col in range(self.col_limit):
                if (row, col) in self.seem:
                    continue
                maximum = max(maximum, self._dfs(row, col))
        return maximum

    def _dfs(self, row, col):
        if (row, col) in self.seem:
            return 0

        area = 0
        if self.grid[row][col] == 1:
            area += 1
            self.seem.add((row, col))
            if row - 1 >= 0:
                area += self._dfs(row-1, col)
            if row + 1 < self.row_limit:
                area += self._dfs(row+1, col)
            if col - 1 >= 0:
                area += self._dfs(row, col-1)
            if col + 1 < self.col_limit:
                area += self._dfs(row, col+1)

        return area

BFS

from collections import deque


class Solution:
    def __init__(self):
        self.grid = []
        self.seem = set()
        self.row_limit = 0
        self.col_limit = 0

    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        self.grid = grid
        self.seem = set()
        self.row_limit = len(grid)
        self.col_limit = len(grid[0])

        maximum = 0
        for row in range(self.row_limit):
            for col in range(self.col_limit):
                if (row, col) in self.seem:
                    continue
                maximum = max(maximum, self._bfs(row, col))
        return maximum

    def _bfs(self, start_row, start_col):
        if (start_row, start_col) in self.seem:
            return 0

        area = 0
        queue = deque([(start_row, start_col)])

        while queue:
            row, col = queue.popleft()
            if (row, col) in self.seem:
                continue

            if self.grid[row][col] == 1:
                area += 1
                self.seem.add((row, col))

                if row - 1 >= 0:
                    queue.append((row-1, col))
                if row + 1 < self.row_limit:
                    queue.append((row+1, col))
                if col - 1 >= 0:
                    queue.append((row, col-1))
                if col + 1 < self.col_limit:
                    queue.append((row, col+1))

        return area