这种要用到传参引用的用 js 写起来比价麻烦,所以就用 c++ 了
// 从边界开始遍历,只要能走到的地方全部标0,然后统计数组里1的个数
class Solution
{
public:
void dfs(vector<vector<int>> &A, int i, int j)
{
if (i < 0 || j < 0 || i == A.size() || j == A[i].size() || A[i][j] != 1)
return;
A[i][j] = 0;
dfs(A, i + 1, j), dfs(A, i - 1, j), dfs(A, i, j + 1), dfs(A, i, j - 1);
}
int numEnclaves(vector<vector<int>> &A)
{
for (int i = 0; i < A.size(); ++i)
dfs(A, i, 0), dfs(A, i, A[i].size() - 1);
for (int j = 0; j < A[0].size(); ++j)
dfs(A, 0, j), dfs(A, A.size() - 1, j);
int res = 0;
for (int i = 0; i < A.size(); ++i)
{
for (int j = 0; j < A[0].size(); ++j)
{
if (A[i][j] == 1)
++res;
}
}
return res;
}
};
// 这是 discuss 一个人的做法, 虽然感觉是繁琐了点,但还是拿上来看一看,很多这种题都是以这个为模板的.
class Solution
{
public:
int numEnclaves(vector<vector<int>> &A)
{
int res = 0;
for (int i = 0; i < A.size(); ++i)
{
for (int j = 0; j < A[0].size(); ++j)
{
bool t = false; // passing this as refrence and as soon as we try to cross boundry we set it true;
int c = 0; // passing this as refrence and increment it for each land piece in the perticular connected component
help(A, i, j, t, c);
if (!t)
res += c; // if we could not cross boundary we add size of connected component to our ans
}
}
return res;
}
void help(vector<vector<int>> &A,int i,int j,bool &t,int &c)
{
if (i < 0 || i >= A.size() || j < 0 || j >= A[0].size())
{
t = true; //we try to cross boundary so set t =true;
return;
}
if (A[i][j] == 0)
{
return;
}
else
{
c++; //increase size of the component
A[i][j] = 0; // mark it visited
// search is four directions
help(A, i + 1, j, t, c);
help(A, i, j + 1, t, c);
help(A, i, j - 1, t, c);
help(A, i - 1, j, t, c);
}
}
};