題目描述
你有一張某海域NxN像素的照片，".“表示海洋、”#"表示陸地，如下所示：

…
.##…
.##…
…##.
…####.
…###.
…

其中"上下左右"四個方向上連在一起的一片陸地組成一座島嶼。例如上圖就有2座島嶼。

由于全球變暖導致了海面上升，科學家預測未來幾十年，島嶼邊緣一個像素的范圍會被海水淹沒。具體來說如果一塊陸地像素與海洋相鄰(上下左右四個相鄰像素中有海洋)，它就會被淹沒。

例如上圖中的海域未來會變成如下樣子：

…
…
…
…
…#…
…
…

請你計算：依照科學家的預測，照片中有多少島嶼會被完全淹沒。
輸入
第一行包含一個整數N。 (1 <= N <= 1000)
以下N行N列代表一張海域照片。

照片保證第1行、第1列、第N行、第N列的像素都是海洋。
輸出
一個整數表示答案。
樣例輸入
7
…
.##…
.##…
…##.
…####.
…###.
…
樣例輸出
1
思路：對于每一個連通塊，都要判斷和海水相鄰的陸地元素數和這個連通塊總共的陸地元素數是否相等，如果想等的話，這個島嶼就會消失，否則就不會消失。
代碼如下：

#include<bits/stdc++.h> #define ll long long using namespace std;const int maxx=1e3+100; int d[][2]={{1,0},{0,1},{-1,0},{0,-1}}; char s[maxx][maxx]; int vis[maxx][maxx]; int n;inline void dfs(int x,int y,int &num,int &cnt) {vis[x][y]=1;num++;if(x-1>=0&&s[x-1][y]=='.') cnt++;else if(x+1<n&&s[x+1][y]=='.') cnt++;else if(y-1>=0&&s[x][y-1]=='.') cnt++;else if(y+1<n&&s[x][y+1]=='.') cnt++;for(int i=0;i<4;i++){int tx=x+d[i][0];int ty=y+d[i][1];if(tx<0||tx>=n||ty<0||ty>=n||vis[tx][ty]||s[tx][ty]=='.') continue;dfs(tx,ty,num,cnt);} } int main() {scanf("%d",&n);for(int i=0;i<n;i++) scanf("%s",s[i]);memset(vis,0,sizeof(vis));int ans=0;for(int i=0;i<n;i++){for(int j=0;j<n;j++){if(s[i][j]=='#'&&vis[i][j]==0){int num=0,cnt=0;dfs(i,j,num,cnt);if(num==cnt) ans++;}}}printf("%d\n",ans);return 0; }

努力加油a啊，(^o)/~

總結

以上是生活随笔為你收集整理的[蓝桥杯][2018年第九届真题]全球变暖（DFS）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。