# Side length of the island (DFS / iteration)

There are many ideas for this question. Because I have recently studied DFS, my first idea is DFS

The following is the code I wrote (very lengthy (not very good idea))

My first thought: when I encounter 1, I will enter the depth search of the island. I will traverse every piece of land up, down, left and right. If there is cross-border or water on the land in these directions, my count + + (mark this land at the same time)

Then continue the deep search

Finally, output the counting result

```class Solution {
public:
int n, m, tx, ty, nextt[4][2] = { {0,1},{1,0},{0,-1},{-1,0} };
int cn = 0;
vector<vector<int> >book;

void dfs(vector<vector<int> >& grid, vector<vector<int> >& book, int n, int m, int x, int y)
{
if (grid[x][y] == 1)
{
book[x][y] = 1;
for (int i = 0; i < 4; i++)
{
tx = x + nextt[i][0];
ty = y + nextt[i][1];

if (tx < 0 || ty < 0 || tx >= n || ty >= m) {
cn++;
book[x][y] = 1;
continue;
}

if (grid[tx][ty] == 0)
cn++;
}
for (int i = 0; i < 4; i++)
{
tx = x + nextt[i][0];
ty = y + nextt[i][1];
if (tx < 0 || ty < 0 || tx >= n || ty >= m || grid[tx][ty] == 0 || book[tx][ty] == 1)
continue;
dfs(grid, book, n, m, tx, ty);
}
}
return;
}

int islandPerimeter(vector<vector<int>>& grid) {
n = grid.size();
m = grid[0].size();
book = vector<vector<int> >(n, vector<int>(m, 0));
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (grid[i][j] == 1&&book[i][j]==0)
{
dfs(grid, book, n, m, i, j);
}
}
}
return cn;
}
};
```

The following code is the official explanation of DFS practice (the idea is the same as me, but the writing method is different)

At this time, the traversal method can be extended to count the perimeter of multiple islands. It should be noted that in order to prevent the land grid from being repeatedly traversed in the depth first search, leading to an endless loop, we need to mark the traversed land grid as traversed. In the following code, the grid with the value of 2 ， is the traversed land grid

```class Solution {
constexpr static int dx[4] = {0, 1, 0, -1};
constexpr static int dy[4] = {1, 0, -1, 0};
public:
int dfs(int x, int y, vector<vector<int>> &grid, int n, int m) {
if (x < 0 || x >= n || y < 0 || y >= m || grid[x][y] == 0) {
return 1;
}
if (grid[x][y] == 2) {
return 0;
}
grid[x][y] = 2;
int res = 0;
for (int i = 0; i < 4; ++i) {
int tx = x + dx[i];
int ty = y + dy[i];
res += dfs(tx, ty, grid, n, m);
}
return res;
}
int islandPerimeter(vector<vector<int>> &grid) {
int n = grid.size(), m = grid[0].size();
int ans = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (grid[i][j] == 1) {
ans += dfs(i, j, grid, n, m);
}
}
}
return ans;
}
};
```

I found the following idea in other people's problem solutions (very simple idea)

We directly traverse the whole array. If we encounter land, we will check whether the land on the top of the land is land and whether the land on the left of the land is land, that is, check the number of contiguous land. We know that land contiguity will occupy two sides, so our final answer is - land number * 4 - contiguous land number * 2

```class Solution {
public:
int ans=0;
int islandPerimeter(vector<vector<int>>& grid) {
if(grid.size()==0)
return 0;
for(int i=0;i<grid.size();i++)
{
for(int j=0;j<grid[0].size();j++)
{
if(grid[i][j]==1)
{
ans+=4;

if(j>0&&grid[i][j-1]==1)
{
ans-=2;
}
if(i>0&&grid[i-1][j]==1)
{
ans-=2;
}
}

}
}
return ans;
}
};```

The following code uses iteration. In fact, it is consistent with the idea of DFS algorithm above. It just doesn't use recursion to directly traverse the array. I won't go into too much detail here~~~

```class Solution {
public://iteration
int islandPerimeter(vector<vector<int>>& grid) {
int n=grid.size();
int m=grid[0].size();
int nextt[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
int tx,ty;
int ans=0,cn=0;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(grid[i][j]==1)
{
cn=0;
for(int z=0;z<4;z++)
{
tx=i+nextt[z][0];
ty=j+nextt[z][1];
if(tx<0||ty<0||tx>=n||ty>=m||!grid[tx][ty])
{
cn++;
}
}
ans+=cn;
}
}
}
return ans;
}
};```

Keywords: Algorithm

Added by Synergic on Wed, 02 Mar 2022 06:57:22 +0200