[蓝桥杯 2018 省 AB] 全球变暖

Luogu

IDLGP8662

Time1000ms

Memory256MB

DifficultyP2

2018广度优先搜索 BFS蓝桥杯省赛

你有一张某海域 $N \times N$ 像素的照片，`.` 表示海洋、 `#` 表示陆地，如下所示： ``` ....... .##.... .##.... ....##. ..####. ...###. ....... ``` 其中 "上下左右" 四个方向上连在一起的一片陆地组成一座岛屿。例如上图就有 $2$ 座岛屿。由于全球变暖导致了海面上升，科学家预测未来几十年，岛屿边缘一个像素的范围会被海水淹没。具体来说如果一块陆地像素与海洋相邻（上下左右四个相邻像素中有海洋），它就会被淹没。例如上图中的海域未来会变成如下样子： ``` ....... ....... ....... ....... ....#.. ....... ....... ``` 请你计算：依照科学家的预测，照片中有多少岛屿会被完全淹没。 ## Input 第一行包含一个整数 $N$。$(1 \le N \le 1000)$。以下 $N$ 行 $N$ 列代表一张海域照片。照片保证第 $1$ 行、第 $1$ 列、第 $N$ 行、第 $N$ 列的像素都是海洋。 ## Output 一个整数表示答案。 [samples] ## Note 时限 1 秒, 256M。蓝桥杯 2018 年第九届省赛

Samples

Input #1

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

Output #1

API Response (JSON)

{
  "problem": {
    "name": "[蓝桥杯 2018 省 AB] 全球变暖",
    "description": {
      "content": "你有一张某海域 $N \\times N$ 像素的照片，`.` 表示海洋、 `#` 表示陆地，如下所示： ``` ....... .##.... .##.... ....##. ..####. ...###. ....... ``` 其中 \"上下左右\" 四个方向上连在一起的一片陆地组成一座岛屿。例如上图就有 $2$ 座岛屿。 由于全球变暖导致了海面上升，科学家预测未来几十年，岛屿边缘一个像素的",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": {
      "LuoguStyle": "P2"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8662"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "你有一张某海域 $N \\times N$ 像素的照片，`.` 表示海洋、 `#` 表示陆地，如下所示：\n\n```\n.......\n.##....\n.##....\n....##.\n..####.\n...###.\n.......\n```\n\n其中 \"上下左右\" 四个方向上连在一起的一片陆地组成一座岛屿。例如上图就有 $2$ 座岛屿。\n\n由于全球变暖导致了海面上升，科学家预测未来几十年，岛屿边缘一个像素的...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments