求海岸线-dfs

本文主要是介绍求海岸线-dfs，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

小莱获得了大奖：CM世界中一片 $n\times m$ 的海域的使用权！这片海域可以看成 $n\times m$ 的格子。其中每个格子要么是海，要么是岛屿，相邻的岛屿可以相互构成一片大的岛屿（相邻是指上下左右相连，斜着相连不算）。小莱现在想知道，他的这片海域中，所有的岛屿的海岸线有多长呢？

小莱获得了大奖：CM世界中一片 $n\times m$ 的海域的使用权！这片海域可以看成 $n\times m$ 的格子。其中每个格子要么是海，要么是岛屿，相邻的岛屿可以相互构成一片大的岛屿（相邻是指上下左右相连，斜着相连不算）。小莱现在想知道，他的这片海域中，所有的岛屿的海岸线有多长呢？

注意：岛中岛不算海岸线。

分析

首先如果岛屿能通过这条边走到边界，则这条边为海岸线，所以我们可以将能到边界的所有点求出来，如果这个点的上、下、左、右有 $1$，则他的上、下、左、右是 $1$ 的点就为海岸线。

代码

#include <bits/stdc++.h>using namespace std;const int N = 1005;
int n, m, vis[N][N], a[N][N];
int dx[] = {0, 0, -1, 1}, dy[] = {-1, 1, 0, 0};void dfs(int x, int y){vis[x][y] = true;for(int i = 0; i < 4; i ++){int nx = x + dx[i], ny = y + dy[i];if(nx >= 0 && nx <= n + 1 && ny >= 0 && ny <= m + 1 && !vis[nx][ny] && !a[nx][ny]){dfs(nx, ny);}}
} int main(){cin >> n >> m;for(int i = 1; i <= n; i ++){for(int j = 1; j <= m; j ++){cin >> a[i][j];}}dfs(0, 0);int ans = 0;for(int i = 0; i <= n + 1; i ++){for(int j = 0; j <= m + 1; j ++){if(vis[i][j]){for(int k = 0; k < 4; k ++){int nx = i + dx[k], ny = j + dy[k];if(nx >= 0 && nx <= n + 1 && ny >= 0 && ny <= m + 1 && a[nx][ny] == 1){ans ++;}}				}}}cout << ans;return 0;
}

这篇关于求海岸线-dfs的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---