Leetcode 1073 Solution

This article provides solution to leetcode question 1073 (number-of-enclaves)
Categories:
Tags:
Access this page by simply typing in "lcs 1073" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/number-of-enclaves

Solution

class Solution:
    def numEnclaves(self, A: List[List[int]]) -> int:
        m = len(A)
        n = len(A[0])

        def mark_margin(A, i, j, m, n):
            if A[i][j] != 1:
                return

            q = [(i, j)]
            A[i][j] = 2

            while q:
                i, j = q.pop(0)

                if i > 0 and A[i - 1][j] == 1:
                    q.append((i - 1, j))
                    A[i - 1][j] = 2
                if i < m - 1 and A[i + 1][j] == 1:
                    q.append((i + 1, j))
                    A[i + 1][j] = 2
                if j > 0 and A[i][j - 1] == 1:
                    q.append((i, j - 1))
                    A[i][j - 1] = 2
                if j < n - 1 and A[i][j + 1] == 1:
                    q.append((i, j + 1))
                    A[i][j + 1] = 2

        for i in range(0, m):
            mark_margin(A, i, 0, m, n)
            mark_margin(A, i, n - 1, m, n)

        for j in range(0, n):
            mark_margin(A, 0, j, m, n)
            mark_margin(A, m - 1, j, m, n)

        ans = 0
        for i, j in itertools.product(range(0, m), range(0, n)):
            if A[i][j] == 1:
                ans += 1
        return ans