具体出处

蓝桥杯2018年cpp组

【第九届】【省赛】【B组】

P8662 [蓝桥杯 2018 省 AB] 全球变暖 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目描述

你有一张某海域 NxN 像素的照片，"."表示海洋、"#"表示陆地，如下所示：

.......

.##....

.##....

....##.

..####.

...###.

.......

其中"上下左右"四个方向上连在一起的一片陆地组成一座岛屿。例如上图就有 2 座岛屿。

由于全球变暖导致了海面上升，科学家预测未来几十年，岛屿边缘一个像素的范围会被海水淹没。具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋)，它就会被淹没。

例如上图中的海域未来会变成如下样子：

.......

.......

.......

.......

....#..

.......

.......

请你计算：依照科学家的预测，照片中有多少岛屿会被完全淹没。

输入描述

第一行包含一个整数 N (1≤N≤1000)。

以下 N 行 N 列代表一张海域照片。

照片保证第 1 行、第 1 列、第 N 行、第 N 列的像素都是海洋。

输出一个整数表示答案。

输入输出样例

示例

输入

7
.......
.##....
.##....
....##.
..####.
...###.
.......

输出

1

运行限制

• 最大运行时间：1s

• 最大运行内存: 256M

这是经典的错误（37分wa了）

#include
using namespace std;int n, ans1, ans2;
bool g[1005][1005], st[1005][1005];
int zwx[] = {1,-1,0,0};
int zwy[] = {0,0,1,-1};string s;void dfs(int x, int y){for(int i = 0; i<4; ++i){int nx = x + zwx[i];int ny = y + zwy[i];if(nx<1 || ny<1 || nx>n || ny>n || st[nx][ny]==0) continue;st[nx][ny] = 0;dfs(nx, ny);}
}int main(){//读图 cin>>n;for(int i = 1; i<=n; ++i){cin>>s;for(int j = 0; jn || ny>n) continue;if(g[nx][ny]==0){st[i][j] = 0;break;}}}}
//    //debug
//    for(int i = 1; i<=n; ++i){
//        for(int j = 1; j<=n; ++j){
//            cout<

错因：一个岛屿部分淹没后可能会生成多个岛屿，答案并不是前后岛屿数量作差。

AC代码

#include
using namespace std;int n, ans1, ans2;
bool g[1005][1005], st[1005][1005], flag;
int zwx[] = {1,-1,0,0};
int zwy[] = {0,0,1,-1};string s;void dfs(int x, int y){//检验四周int k = 0; for(k; k<4; ++k){int nx = x + zwx[k];int ny = y + zwy[k];if(nx<1 || ny<1 || nx>n || ny>n) continue;if(g[nx][ny]==0){break;}}if(k==4) flag = 1;//走位 for(int i = 0; i<4; ++i){int nx = x + zwx[i];int ny = y + zwy[i];if(nx<1 || ny<1 || nx>n || ny>n || st[nx][ny]==0) continue;st[nx][ny] = 0;dfs(nx, ny);}
}int main(){//读图 cin>>n;for(int i = 1; i<=n; ++i){cin>>s;for(int j = 0; j