求海岸线-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;
}