蓝桥杯寒假集训第四天(全球变暖DFS)
2023-02-19 12:20:07 时间
没有白走的路,每一步都算数???
题目描述:
有一个正方形区域,里面有大陆和海洋,暂且用‘.’表示海洋,用‘#’表示大陆。我们把上下左右都连在一起的大陆称之为岛屿。但是随着气温的升高,有些沿海岛屿的大陆会被海洋给吞噬。问在大海咆哮之后,有多少的岛屿被完全淹没。
输入描述:
第一行:
输入一个数n,表示方形区域的边长
接下来n行:
输入n个符号,可以是‘.’,也可以是‘#’。‘.’表示海洋;‘#’表示大陆;
输出描述:
输出最后还存在的岛屿数目t
样例输入输出:
样例输入:
样例输出:
1
算法设计思路:
当遇见‘#’我们就认为多了一个岛屿,当这个岛屿的上下左右都是‘#’时候,我们认为这个岛屿不会被淹没。并且将中间的大陆做一个标记。然后对上下左右四个方位的点分别进行判断,如果满足条件再进行递归。
段错误
第一感觉认为这个和指针越界有关,于是在if条件语句中增设门槛,但依旧段错误。遂查找文献,发现是有递归栈满的嫌疑。然后通过设置参数,结果成功
文末有参考文献
最终AC代码:
#全球变暖
import sys
n = int(input())
L = []
res_ans = 0# 所有的岛屿数目
ans = 0#没有被淹没的岛屿数目
sys.setrecursionlimit(100000)
for i in range(n):
L.append(list(input()))
flag = False
d = [[1,0],[-1,0],[0,1],[0,-1]]
def dfs(x,y):
global flag
global ans
if flag==False:
cnt = 0
for i in range(4):
newx = x+d[i][0]
newy = y+d[i][1]
if newx>=0 and newx<n and newy >=0 and newy <n:
if L[newx][newy]!='.':
cnt+=1
if cnt==4:
flag = True
ans+=1
L[x][y] = '*'
for i in range(4):
xx = x+d[i][0]
yy = y+d[i][1]
if xx>=0 and xx <n and yy>=0 and yy<n:
if L[xx][yy] == '#':
dfs(xx,yy)
for i in range(n):
for j in range(n):
if L[i][j] == '#':
res_ans+=1
flag = False
dfs(i,j)
print(res_ans-ans)
python dfs bfs迷宫_AcWing 1112. 迷宫DFS-Python版本(DFS递归深度限制)_weixin_39822993的博客-CSDN博客
每日一句
摘自《《晚熟的人》》:
世界上的事儿就是这样,无论多么高的山,也有鸟飞过去;无论多么密的网,也有鱼钻过去
相关文章
- Jgit的使用笔记
- 利用Github Action实现Tornadofx/JavaFx打包
- 叹息!GitHub Trending 即将成为历史!
- 微软软了?开源社区讨论炸锅,GitHub CEO 亲自来答
- GitHub Trending 列表频现重复项,前后端都没去重?
- Photoshop Elements 2021版本软件安装教程(mac+windows全版本都有)
- (ps全版本)Photoshop 2020的安装与破解教程(mac+windows全版本都有)
- (ps全版本)Photoshop cc2018的安装与破解教程(mac+windows全版本,包括2023
- 环境搭建:Oracle GoldenGate 大数据迁移到 Redshift/Flat file/Flume/Kafka测试流程
- 每个开发人员都要掌握的:最小 Linux 基础课
- 来撸羊毛了!Windows 环境下 Hexo 博客搭建,并部署到 GitHub Pages
- 超实用!手把手入门 MongoDB:这些坑点请一定远离
- 【GitHub日报】22-10-09 zustand、neovim、webtorrent、express 等4款App今日上新
- 【GitHub日报】22-10-10 brew、minio、vite、seaweedfs、dbeaver 等8款App今日上新
- 【GitHub日报】22-10-11 cobra、grafana、vue、ToolJet、redwood 等13款App今日上新
- Photoshop 2018 下载及安装教程(mac+windows全版本都有,包括最新的2023)
- Photoshop 2017 下载及安装教程(mac+windows全版本都有,包括最新的2023)
- Photoshop 2020 下载及安装教程(mac+windows全版本都有,包括最新的2023)
- Photoshop 2023 资源免费下载(mac+windows全版本都有,包括最新的2023)
- 最新版本Photoshop CC2018软件安装教程(mac+windows全版本都有,包括2023