蓝桥杯-全球变暖-python

简介: 蓝桥杯-全球变暖-python

你有一张某海域 N×N 像素的照片,”.”表示海洋、”#”表示陆地,如下所示:

.##…

.##…

…##.

…####.

…###.

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

由于全球变暖导致了海面上升,科学家预测未来几十年,岛屿边缘一个像素的范围会被海水淹没。

具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋),它就会被淹没。

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

…#…

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

输入格式

第一行包含一个整数N。

以下 N 行 N 列,包含一个由字符”#”和”.”构成的 N×N 字符矩阵,代表一张海域照片,”#”表示陆地,”.”表示海洋。

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

输出格式

一个整数表示答案。

数据范围

1≤N≤1000

输入样例1:

7


1. …
2. .##…
3. .##…
4. …##.
5. …####.
6. …###.
7. …


输出样例1:

1

输入样例2:


1. 9
2. …
3. .##.##…
4. .#####…
5. .##.##…
6. …
7. .##.#…
8. .#.###…
9. .#…#…
10. …

输出样例2:

1

 

思路

对所给图片的每一个点进行宽度搜索。设置flag,如果flag==0,说明不被淹没,否则被淹没。

如果一块地周围都是土地,那么他最终不会被淹没。

标记搜算过的土地,避免重复搜索。

搜索当前土地相邻的未标记的土地,直到搜完这块岛屿为止


代码


1. def bfs(i,j):
2.   d=[(0,1),(0,-1),(1,0),(-1,0)]
3.   q=[(i,j)]
4.   vis[i][j]=1
5. global flag
6.   while q:
7.     t=q.pop(0)
8.     tx,ty=t[0],t[1]
9. if mp[tx][ty+1]=='#' and mp[tx][ty-1]=='#' and mp[tx-1][ty]=='#' and mp[tx+1][ty]=='#':
10.       flag=1
11. for n in range(4):
12.       nx=tx+d[n][0]
13.       ny=ty+d[n][1]
14. if vis[nx][ny]==0 and mp[nx][ny]=="#":
15.         q.append((nx,ny))
16.         vis[nx][ny]=1
17. 
18. n=int(input())
19. mp=[]
20. for i in range(n):
21.   mp.append(list(input()))
22. 
23. vis = []
24. for i in range(n):
25.     vis.append([0]*n)
26. 
27. ans=0
28. for i in range(n):
29. for j in range(n):
30. if vis[i][j]==0 and mp[i][j]=='#':
31.       flag=0
32.       bfs(i,j)
33. if flag==0:
34.         ans+=1
35. print(ans)
目录
相关文章
|
5月前
|
Python
蓝桥杯练习题(一):Python组之入门训练题
这篇文章是关于蓝桥杯Python组的入门训练题,包括Fibonacci数列、圆的面积、序列求和和A+B问题的具体代码实现和样例输出。
187 0
|
5月前
|
存储 机器学习/深度学习 算法
蓝桥杯练习题(三):Python组之算法训练提高综合五十题
蓝桥杯Python编程练习题的集合,涵盖了从基础到提高的多个算法题目及其解答。
206 3
蓝桥杯练习题(三):Python组之算法训练提高综合五十题
|
5月前
|
人工智能 Python
蓝桥杯练习题(四):Python组之历届试题三十题
关于蓝桥杯Python组历届试题的三十个练习题的总结,包括题目描述、输入输出格式、样例输入输出以及部分题目的解题思路和代码实现。
146 0
蓝桥杯练习题(四):Python组之历届试题三十题
|
5月前
|
存储 机器学习/深度学习 算法
蓝桥杯练习题(二):Python组之基础练习三十题
蓝桥杯Python编程练习题的集合,包含了三十个不同难度的编程题目,覆盖了基础语法、数据结构和算法等领域。
103 0
|
10月前
|
索引 Python 容器
【备战蓝桥杯】探索Python内置标准库collections的使用
【备战蓝桥杯】探索Python内置标准库collections的使用
125 1
|
10月前
|
开发者 Python
【备战蓝桥杯】如何使用Python 内置模块datetime去计算我与CSDN相遇的天数
【备战蓝桥杯】如何使用Python 内置模块datetime去计算我与CSDN相遇的天数
104 1
|
10月前
|
算法 测试技术 编译器
蓝桥杯-02-python组考点与14届真题
蓝桥杯-02-python组考点与14届真题
|
10月前
|
Python
第十三届蓝桥杯B组python(试题A:排列字母)
第十三届蓝桥杯B组python(试题A:排列字母)
91 0
|
10月前
|
人工智能 算法 测试技术
第十四届蓝桥杯第三期模拟赛 【python】(二)
第十四届蓝桥杯第三期模拟赛 【python】(二)
|
10月前
|
测试技术 Python
第十四届蓝桥杯第三期模拟赛 【python】(一)
第十四届蓝桥杯第三期模拟赛 【python】(一)

热门文章

最新文章