|
| 1 | +#!/usr/bin/python3 |
| 2 | +""" |
| 3 | +Given a 2D array A, each cell is 0 (representing sea) or 1 (representing land) |
| 4 | +
|
| 5 | +A move consists of walking from one land square 4-directionally to another land |
| 6 | +square, or off the boundary of the grid. |
| 7 | +
|
| 8 | +Return the number of land squares in the grid for which we cannot walk off the |
| 9 | +boundary of the grid in any number of moves. |
| 10 | +
|
| 11 | +Example 1: |
| 12 | +Input: [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]] |
| 13 | +Output: 3 |
| 14 | +Explanation: |
| 15 | +There are three 1s that are enclosed by 0s, and one 1 that isn't enclosed |
| 16 | +because its on the boundary. |
| 17 | +
|
| 18 | +Example 2: |
| 19 | +Input: [[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]] |
| 20 | +Output: 0 |
| 21 | +Explanation: |
| 22 | +All 1s are either on the boundary or can reach the boundary. |
| 23 | +
|
| 24 | +Note: |
| 25 | +1 <= A.length <= 500 |
| 26 | +1 <= A[i].length <= 500 |
| 27 | +0 <= A[i][j] <= 1 |
| 28 | +All rows have the same size. |
| 29 | +""" |
| 30 | +fromtypingimportList |
| 31 | + |
| 32 | + |
| 33 | +dirs= ((0,-1), (0,1), (1,0), (-1,0)) |
| 34 | + |
| 35 | + |
| 36 | +classSolution: |
| 37 | +defnumEnclaves(self,A:List[List[int]])->int: |
| 38 | +""" |
| 39 | + not dfs from any cell, but dfs from the edges |
| 40 | + """ |
| 41 | +m,n=len(A),len(A[0]) |
| 42 | +visited= [[Falsefor_inrange(n)]for_inrange(m)] |
| 43 | +foriinrange(m): |
| 44 | +forjinrange(n): |
| 45 | +ifnotvisited[i][j]andA[i][j]==1and (i==0orj==0ori==m-1orj==n-1): |
| 46 | +self.dfs(A,i,j,visited) |
| 47 | + |
| 48 | +ret=0 |
| 49 | +foriinrange(m): |
| 50 | +forjinrange(n): |
| 51 | +ifA[i][j]==1andnotvisited[i][j]: |
| 52 | +ret+=1 |
| 53 | +returnret |
| 54 | + |
| 55 | +defdfs(self,A,i,j,visited): |
| 56 | +m,n=len(A),len(A[0]) |
| 57 | +visited[i][j]=True |
| 58 | +fordi,djindirs: |
| 59 | +I=i+di |
| 60 | +J=j+dj |
| 61 | +if0<=I<mand0<=J<nandnotvisited[I][J]andA[I][J]==1: |
| 62 | +self.dfs(A,I,J,visited) |
| 63 | + |
| 64 | + |
| 65 | +classSolutionError: |
| 66 | +def__init__(self): |
| 67 | +self.ret=0 |
| 68 | + |
| 69 | +defnumEnclaves(self,A:List[List[int]])->int: |
| 70 | +""" |
| 71 | + dfs coloring |
| 72 | + """ |
| 73 | +m,n=len(A),len(A[0]) |
| 74 | +visited= [[Nonefor_inrange(n)]for_inrange(m)]# 0 not off, 1 off |
| 75 | +foriinrange(m): |
| 76 | +forjinrange(n): |
| 77 | +ifnotvisited[i][j]andA[i][j]==1: |
| 78 | +self.dfs(A,i,j,visited) |
| 79 | +returnself.ret |
| 80 | + |
| 81 | +defdfs(self,A,i,j,visited): |
| 82 | +m,n=len(A),len(A[0]) |
| 83 | +visited[i][j]=0 |
| 84 | +fordi,djindirs: |
| 85 | +I=i+di |
| 86 | +J=j+dj |
| 87 | +ifnot (0<=I<mand0<=J<n): |
| 88 | +visited[i][j]=1 |
| 89 | +returnTrue |
| 90 | +ifvisited[I][J]==1: |
| 91 | +visited[i][j]=1 |
| 92 | +returnTrue |
| 93 | +ifvisited[I][J]isNoneandA[I][J]==1andself.dfs(A,I,J,visited): |
| 94 | +visited[i][j]=1 |
| 95 | +returnTrue |
| 96 | + |
| 97 | +self.ret+=1 |
| 98 | +returnFalse |