Description
Given a 2D array A, each cell is 0 (representing sea) or 1 (representing land)
A move consists of walking from one land square 4-directionally to another land square, or off the boundary of the grid.
Return the number of land squares in the grid for which we cannot walk off the boundary of the grid in any number of moves.
给出一个二维数组 A，每个单元格为 0（代表海）或 1（代表陆地）。
移动是指在陆地上从一个地方走到另一个地方（朝四个方向之一）或离开网格的边界。
返回网格中无法在任意次数的移动中离开网格边界的陆地单元格的数量。
题目链接：https://leetcode.com/problems/number-of-enclaves/
Difficulty: medium
Example 1:
Input: [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]
Output: 3
Explanation:
There are three 1s that are enclosed by 0s, and one 1 that isn't enclosed because its on the boundary.
Example 2:
Input: [[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]
Output: 0
Explanation:
All 1s are either on the boundary or can reach the boundary.
Note:
- 1 <= A.length <= 500
- 1 <= A[i].length <= 500
- 0 <= A[i][j] <= 1
- All rows have the same size.
分析
- 定义walk函数，若当前点对应land，修改为sea，同时将其四个方向相邻的land进入到下一个walk中；
- judge函数用于判断（x,y）位置是超出数组范围；
- 遍历数组的四条边缘，将land的点用walk函数修改；
- 返回A的和，即land的个数。
参考代码
class Solution(object):
def numEnclaves(self, A):
row=len(A)
col=len(A[0])
def judge(x,y):
return True if(x>=0 and x<row and y>=0 and y<col) else False
def walk(x,y):
if(judge(x,y) and A[x][y]==1):
A[x][y]=0
walk(x-1,y)
walk(x+1,y)
walk(x,y-1)
walk(x,y+1)
index=1
for i in [0,row-1]:
for j in range(col):
if(A[i][j]!=0):
walk(i,j)
for i in range(row):
for j in [0,col-1]:
if(A[i][j]!=0):
walk(i,j)
return sum([sum(a) for a in A])