小工具知识网

当前位置: 首页 > 行业知识 > 算法-双指针、BFS与图论-1113. 红与黑

行业知识

算法-双指针、BFS与图论-1113. 红与黑

2026-11-17 08:44:57 来源:互联网转载

题目

思路

  1. 本题相当于问BFS中的当前点所在的区域连通块有多少个 ==Flood Fill算法 (可参考以下链接:洪水覆盖算法(Flood Fill):颜色填充-CSDN博客)
  2. 本题用DFS实现Flood Fill算法
  3. DFS���否需要恢复现场:(重要!!!!!)
    AcWing 842. 通过全排列问题 深入探讨DFS回溯以及恢复现场的本质 - AcWing
    判断DFS是否需要恢复现场_dfs 不用还原现场-CSDN博客

代码

# 搜索的四个方向dx =[-1,0,1,0]dy =[0,1,0,-1]def dfs(x,y):    # 初始化相关的参数:连通块个数,访问数组等;    cnt = 1    st[x][y]=True    # 四个方向进行搜索    for i in range(4):        a=x+dx[i]        b=y+dy[i]        # 一些条件的判断:是否越界,是否能走,是否走过        if a=n or b=m:            continue;        if g[a][b]!='.':            continue        if st[a][b]:            continue        cnt+=dfs(a,b)    return cntwhile True:    # 读入基本信息    m,n=map(int,input().split())    if n==0 or m==0 :        break    g =[input() for _ in range(n)]        # 获取起始坐标    x,y=0,0    for i in range(n):        for j in range(m):            if g[i][j]=='@':                x,y=i,j    # 设置访问列表    st=[[False] * m for _ in range(n)]      print(dfs(x,y))

上一篇:小红书软件下载攻略,轻松掌握下载步骤,快速上手!

下一篇:苹果音乐下载方法指南