蓝桥杯(3):python搜索DFS

 

目录

1 DFS简介

1.1 DFS与n重循环

1.2 代码实现

1.3 例题

1.3.1 分糖果

1.3.2 买瓜

2 回溯

2.1 定义

2.2 代码实例

2.1.1 排列数

 2.1.2 找子集

2.3 例题

2.3.1 N皇后

2.3.2 小朋友崇拜圈

2.3.3 全球变暖

3 剪枝

3.1 定义

3.2 分类

3.3 例子

3.3.1 数字王国之军训练队

3.3.2 特殊的多边形

4 记忆化搜索

4.1 定义

4.2 例子

4.2.1 斐波那契数列

4.2.2 混沌之地

4.2.3 地宫取宝

1 DFS简介

1.1 DFS与n重循环

DFS 就是枚举 和n重循环

1.2 代码实现

#dfs和n重循环
x = int(input())
n = int(input())
path = [0]*n
#depth从0开始哦！！！

def dfs(depth):

    #depth表示当前的深度！
    #采用递归的思想
    #写递归出口
    if depth == n:

        for i in range(1,n):
            if path[i] >= path[i-1]:
                continue
            else:
                return
        if sum(path) != x:
            return
        
        print(path)
        return

    else:
        for i in range(1,x+1):
            path[depth] = i
            dfs(depth+1)


dfs(0)

1.3 例题

1.3.1 分糖果

#糖果总数
#一共有7个小朋友，9个第一种糖果，16个第二种糖果
ans = 0
def dfs(depth,n,m):
    #depth当前是第几个小朋友
    #n表示剩余几个第一种
    #m表示剩余几个第二种
    if depth == 7:
        if n==0 and m==0:
            global ans
            ans +=1
        # print(ans)
        return
    else:
        for i in range(0,6):
            for j in range(0,6):
                if 2<=i+j<=5 and i <=n and j<=m:
                    dfs(depth+1,n-i,m-j)

dfs(0,9,16)
print(ans)

1.3.2 买瓜

#买瓜

def dfs(depth,weight,cnt):
    #depth表示第depth个瓜
    #weight表示当前的重量
    #cnt表示砍了几刀
    if weight > m:
        return
    if weight == m:
        global ans
        ans = min(ans,cnt)
    if depth == n:
        return
    else:
        #买全部
        dfs(depth+1,weight+a[depth],cnt)
        #卖一半
        dfs(depth+1,weight+a[depth]//2,cnt+1)
        #没买
        dfs(depth+1,weight,cnt)


n,m = list(map(int,input().split()))
a = list(map(int,input().split()))
weight = 0
cnt = 0
m*=2
a = [i*2 for i in a]
ans = n+1
dfs(0,0,0)

if ans == n+1:
    ans = -1

print(ans)

2 回溯

2.1 定义

2.2 代码实例

2.1.1 排列数

回溯：判断是否能选、打标记、记录路径、下一层、回到上一层？？（是怎么回去的啊老铁）清楚标记、清楚路径储存

回到上一层：通过debug我得出：回到上一层其实是递归自己过程中的实现

递归会造成多个函数的运行，只有运行完才会结束！语言描述能力有限，具体可以自己debug一下感受

n = int(input())
vis = [False]*(n+1)
path = []


def dfs(depth):
    if depth == n:
        print(path)
        return
    else:
        for i in range(1,n+1):
            if vis[i]: #如果已经被标记过就不选这个数直接跳出循环！
                continue
            vis[i] = True
            path.append(i)
            dfs(depth+1)
            vis[i] = False
            path.pop(-1)


dfs(0)

 2.1.2 找子集

和买瓜一样，瓜是这个瓜买不买，

子集是，这个数选不选   一模一样！！！哦哦哦

找到人任意集合的所有子集

#求子集
#和卖瓜的一样
n = int(input())
a = list(map(int,input().split()))

path = []

def dfs(depth):
    if depth ==n:
        print(path)
        return
    else:
        #选的话
        path.append(a[depth])
        # print(path)
        dfs(depth+1)
        path.pop(-1)

        #不选的话
        dfs(depth+1)
dfs(0)

2.3 例题

2.3.1 N皇后

不能在同一行同一列和对角线上

# N皇后
#主要是对角线的处理，如果在主对角线上 横纵坐标的值相加为0，在副对角线上横纵坐标相减为0
n = int(input()) #表示有几个皇后
ans = 0
vis1 = [False]*(n+1)
vis2 = [False]*2*(n+1)
vis3 = [False]*2*(n+1)

def dfs(x): #x表示第几行
    if x==n:
        global ans
        ans +=1
        return
    else:
        for y in range(0,n):
            #判断是否能放
            if vis1[y] is False and vis2[x+y] is False and vis3[x-y+n] is False:
                vis1[y] = vis2[x+y] = vis3[x-y+n] = True
                dfs(x+1)
                vis1[y] = vis2[x + y] = vis3[x - y+n] = False
            else:
                continue

dfs(0)
print(ans)

2.3.2 小朋友崇拜圈

就是要围成一个圈！图论的知识相关

从1出发 开始找环，length用于记录步长--走到之后判断是否可以走，如果不可以走说明到了原来走过的点了

#小朋友崇拜环
import sys
sys.setrecursionlimit(10000000) #例如这里设置为十万
def dfs(x,length):
    #从x出发找环
    #length走了多少步
    vis[x] = length  #这个点走了一步现在
    #接下来走下面的点了
    if vis[a[x]] != 0:
        #说明在a[x]这一点形成环了，那么这个点出的length值应该是第一步！
        global ans
        ans = max(ans,length - vis[a[x]] +1)
        return
        #说明下一个点已经走过了
        #这时就要输出环长了

    else:
        #说明可以走
        dfs(a[x], length+1) #步长加1


n = int(input())
a = [0] + list(map(int,input().split()))
vis = [0]*(n+1) #标记该点是否走过
ans = 0
an = []


for i in range(1,n+1):
    dfs(i,1)
print(ans)

2.3.3 全球变暖

高地：上下左右都是#

对于每一个#都看看是不是高地

思路：

1、从左到右 从上到下，对于未标记的陆地“#”做一遍dfs

2、dfs目的：拓展可以到达的所有点，并打上标记

3、可以统计出有多少个岛屿、有多少个高地（上下左右都是#）

#全球变暖
import sys
sys.setrecursionlimit(10000000) #例如这里设置为十万


def dfs(x,y):
    #表示现在搜索的点的坐标
    #标记该点
    vis[x][y]=1
    #判断是不是高低
    if a[x-1][y] == "#" and a[x+1][y] == "#" and a[x][y-1] == "#" and a[x][y+1] == "#" :#说明上下左右都是高低不会被淹没
        global flag
        flag = True

    #把四周的未遍历的土地继续遍历!!!!!!!
    #所有连在一起的就是一座岛屿
    #这个坐标周围如果还有陆地说明他们是一个岛屿 没有结束，接着运行！！！！！！！！！！！！
    for i in range(4):
        xx,yy = x+dir[i][0],y+dir[i][1]
        if 0<=xx <=n-1 and 0<= yy<=n-1:
            if a[xx][yy] == "#" and vis[xx][yy] == 0:
                dfs(xx,yy)
        else:
            continue

#先写输入
dir = [(1,0),(0,1),(-1,0),(0,-1)]
n = int(input())
a = []
vis = [] #表示标记
flag = False#表示是否是高地！
for i in range(n):
    a.append(list(input()))
    vis.append([0]*n)



ans = 0
for i in range(n):
    for j in range(n):
        if a[i][j] == "#" and vis[i][j] == 0:
            flag = False
            dfs(i,j)
            if flag is False:
                ans += 1
print(ans)

3 剪枝

3.1 定义

当前状态无解就不要向下搜索了

3.2 分类

3.3 例子

3.3.1 数字王国之军训练队

把学生分组：

则dfs的参数就是学生

#数字王国之军训练队
#学生分成多少组？--学生————所以depth是学生
n = int(input())
a = list(map(int,input().split()))
group = []

def check(x,group):
    for y in group:
        if x%y==0 or y%x== 0 or x==y:
            return False
    return True


def dfs(depth):
    if depth == n:
        global ans
        ans = min(ans,len(group))
        # print(group)
        return ans

    #放入已有的组中
    for ever_group in group:
        if check(a[depth],ever_group):
            ever_group.append(a[depth])
            dfs(depth+1)
            ever_group.pop(-1)
    #自己变成一个组
    group.append([a[depth]])
    dfs(depth+1)
    group.pop(-1)


#最后要输出一个最小组数
ans = n
dfs(0)
print(ans)

3.3.2 特殊的多边形

#剪枝-特殊的多边形
import sys
sys.setrecursionlimit(100000) #例如这里设置为十万
t,n = list(map(int,input().split()))
a = []
for i in range(t):
    a.append(list(map(int,input().split())))
# print(a)


def dfs(depth,last_i,tot,mul,list):
    if depth == n:
        if tot > 2*path[-1] and list[0] <= mul <= list[1]:
            global ans
            ans += 1
            # print(path)
        return
    else:
        for i in range(last_i+1,100001):
            if mul*(i**(n-depth)) <= list[1]:
                path.append(i)
                dfs(depth+1,i,tot+i,mul*i,list)
                path.pop(-1)
            else:
                break



for list in a:
    path = []
    ans = 0
    dfs(0,1,0,1,list)
    print(ans)

4 记忆化搜索

4.1 定义

4.2 例子

4.2.1 斐波那契数列

考虑使用递归写法，直接递归的时间是指数级别增加的

重复计算的地方发在字典里！

#斐波那契数列
#没有存储的写法
def f(n):
    if n==0:
        return 1
    if n==1:
        return 1
    else:
        return f(n-1)+f(n-2)
n = int(input())
print(f(n))


#存储的写法

dict={0:1,1:1}
def f(n):
    if n in dict.keys():
        return dict[n]
    else:
        dict[n] = f(n-1)+f(n-2)
        return dict[n]
print(f(40))

但是有一个更牛*的

记忆化搜索的第二种方法

#实现把普通的递归变成记忆化的递归
from functools import lru_cache
@lru_cache(maxsize=None)
def f(n):
    if n==0:
        return 1
    if n==1:
        return 1
    else:
        return f(n-1)+f(n-2)
n = int(input())
print(f(n))

4.2.2 混沌之地

dfs的参数确定 ：坐标

from functools import lru_cache
@lru_cache(maxsize=None)
def dfs(x,y,z):
    #x,y 表示当前的坐标
    #z表示喷气背包有没有用
    if x == c and y==d:
        return True
    else:
        for detle_x,detle_y in [(0,1),(1,0),(-1,0),(0,-1)]:
            xx = x+detle_x
            yy = y+detle_y
            if 0<=xx<=n-1 and 0<=yy<=m-1:
                if A[xx][yy] <A[x][y]:
                    dfs(xx,yy,z)
                if A[xx][yy] <A[x][y]+k and z==False:
                    dfs(xx,yy,True)
    return False


#输入
n,m,k = list(map(int,input().split()))
a,b,c,d = list(map(int,input().split()))
a -=1
b -=1
c -=1
d -=1

A = []
for i in range(n):
    A.append(list(map(int,input().split())))


#输出
out = dfs(a,b,False)
if out == True:
    print("Yes")
else:
    print("No")

'''
5 5 30
1 1 5 5
3 20 13 12 11
19 17 33 72 10
12 23 12 23 9
21 43 23 12 2
21 34 23 12 1
'''

4.2.3 地宫取宝

####当没有不使用记忆搜素，并且加入的是当前位置的val值时

def dfs(x,y,tot,w)  :  #在（x,y)的数量tot,最大价值为w
    if x==n and y==m :
        global ans
        if tot==k:
            ans +=1
            return
        
        return


    for delta_x,delta_y in [(0,1),(1,0)]:
        xx,yy=x+delta_x,y+delta_y
        if 0<=xx<=n and 0<=yy<=m:
            if w < val[xx][yy]: #把上一个位置的value加进去了
                dfs(xx,yy,tot+1,val[xx][yy])
            dfs(xx, yy, tot, w)  # 不选择
        else:
            continue
    return

n,m,k=map(int,input().split())
val=[[0]*(m+1)]
for i in range(n):
    val.append([0]+list(map(int,input().split())))
print(val)

ans = 0
dfs(1,1,1,1)
dfs(1,1,0,-1)
print(ans)

###当不使用记忆力搜索，加入的是上一个位置的val值

def dfs(x,y,tot,w)  :  #在（x,y)的数量tot,最大价值为w
    if x==n and y==m :
        global ans
        if tot==k:
            ans +=1
            return
        elif tot==k-1 and w<val[n][m]:
            ans+=1
            return
        return


    for delta_x,delta_y in [(0,1),(1,0)]:
        xx,yy=x+delta_x,y+delta_y
        if 0<=xx<=n and 0<=yy<=m:
            if w < val[x][y]: #把上一个位置的value加进去了
                dfs(xx,yy,tot+1,val[x][y])
            dfs(xx, yy, tot, w)  # 不选择
        else:
            continue
    return

n,m,k=map(int,input().split())
val=[[0]*(m+1)]
for i in range(n):
    val.append([0]+list(map(int,input().split())))
print(val)

ans = 0
dfs(1,1,0,-1)
print(ans)

###当使用记忆力搜索时！！！！【和之前所有的不同的就是return一定要有返回值！！！不能是空了，要不然记忆什么 我请问呢小姐姐】

from functools import lru_cache
@lru_cache(maxsize=None)
def dfs(x,y,tot,w)  :  #在（x,y)的数量tot,最大价值为w
    if x==n and y==m :
        if tot==k:
            return 1
        elif tot==k-1 and w<val[n][m]:
            return 1
        return 0

    ans =0
    for delta_x,delta_y in [(0,1),(1,0)]:
        xx,yy=x+delta_x,y+delta_y
        if 0<=xx<=n and 0<=yy<=m:
            if w < val[x][y]: #把上一个位置的value加进去了
                ans +=dfs(xx,yy,tot+1,val[x][y])
            ans +=dfs(xx, yy, tot, w)  # 不选择
        else:
            continue
    return ans

n,m,k=map(int,input().split())
val=[[0]*(m+1)]
for i in range(n):
    val.append([0]+list(map(int,input().split())))


print(dfs(1,1,0,-1))

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/495448.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

修改 RabbitMQ 默认超时时间

修改 RabbitMQ 默认超时时间

MQ客户端正常运行&#xff0c;突然就报连接错误&#xff0c; 错误信息写的很明确&#xff0c;是客户端连接超时。 不过很疑虑&#xff0c;为什么会出现连接超时呢&#xff1f;代码没动过&#xff0c;网络也ok&#xff0c;也设置了心跳和重连机制。 最终在官网中找到了答案&am…
阅读更多...
【Flutter 面试题】 什么是Flutter插件（Plugin）？如何使用和创建插件？

【Flutter 面试题】 什么是Flutter插件（Plugin）？如何使用和创建插件？

【Flutter 面试题】 什么是Flutter插件&#xff08;Plugin&#xff09;&#xff1f;如何使用和创建插件&#xff1f; 文章目录 写在前面口述回答补充说明使用插件创建插件 写在前面 &#x1f64b; 关于我 &#xff0c;小雨青年 &#x1f449; CSDN博客专家&#xff0c;GitChat…
阅读更多...
MobileVIT原理详解篇

MobileVIT原理详解篇

&#x1f34a;作者简介&#xff1a;秃头小苏&#xff0c;致力于用最通俗的语言描述问题 &#x1f34a;专栏推荐&#xff1a;深度学习网络原理与实战 &#x1f34a;近期目标&#xff1a;写好专栏的每一篇文章 &#x1f34a;支持小苏&#xff1a;点赞&#x1f44d;&#x1f3fc;、…
阅读更多...
国内电力消费增速攀升，新兴产业用电量势头大增

国内电力消费增速攀升，新兴产业用电量势头大增

由中国电力企业联合会主办的2024年经济形势与电力发展分析预测会26日在京举办。中国电力企业联合会常务副理事长杨昆在会上介绍&#xff0c;2023年&#xff0c;国内电力消费增速攀升&#xff0c;新兴产业用电量保持增长势头。全社会用电量达到9.22万亿千瓦时&#xff0c;比2022…
阅读更多...
深入解析《企业级数据架构》：HDFS、Yarn、Hive、HBase与Spark的核心应用

深入解析《企业级数据架构》：HDFS、Yarn、Hive、HBase与Spark的核心应用

写在前面 进入大数据阶段就意味着进入NoSQL阶段&#xff0c;更多的是面向OLAP场景&#xff0c;即数据仓库、BI应用等。 大数据技术的发展并不是偶然的&#xff0c;它的背后是对于成本的考量。集中式数据库或者基于MPP架构的分布数据库往往采用的都是性能稳定但价格较为昂贵的小…
阅读更多...
政安晨：【Keras机器学习实践要点】（六）—— 使用内置方法进行训练和评估

政安晨：【Keras机器学习实践要点】（六）—— 使用内置方法进行训练和评估

政安晨的个人主页&#xff1a;政安晨 欢迎 &#x1f44d;点赞✍评论⭐收藏 收录专栏: TensorFlow与Keras实战演绎机器学习 希望政安晨的博客能够对您有所裨益&#xff0c;如有不足之处&#xff0c;欢迎在评论区提出指正&#xff01; 本文涵盖使用内置 API 进行训练和验证&#…
阅读更多...
微服务（基础篇-006-Docker安装-CentOS7）

微服务（基础篇-006-Docker安装-CentOS7）

目录 05-初识Docker-Docker的安装_哔哩哔哩_bilibilihttps://www.bilibili.com/video/BV1LQ4y127n4?p46&spm_id_frompageDriver&vd_source60a35a11f813c6dff0b76089e5e138cc 0.安装Docker 1.CentOS安装Docker 1.1.卸载&#xff08;可选&#xff09; 1.2.安装dock…
阅读更多...
I2C和EEPROM

I2C和EEPROM

提示&#xff1a;文章 文章目录 前言一、背景二、 2.1 2.2 总结 前言 前期疑问&#xff1a; 本文目标&#xff1a; 一、背景 最近在看I2C通讯&#xff0c;使用的是AT24C02的EEPROM芯片 二、 2.1 设计电路 画了电路图 2.2 程序 2024年3月27日23:10:06 初步配置了I2C …
阅读更多...
【爬虫基础】第4讲 GET与POST请求

【爬虫基础】第4讲 GET与POST请求

GET请求 GET请求是一种HTTP方法&#xff0c;用于向服务器获取&#xff08;或读取&#xff09;数据。它是Web开发中最常用的请求方式之一。对于GET请求&#xff0c;客户端向服务器发送一个HTTP请求&#xff0c;服务器返回请求的资源。GET请求通常用于获取静态资源&#xff0c;比…
阅读更多...
题目：摆花（蓝桥OJ 0389）

题目：摆花（蓝桥OJ 0389）

问题描述&#xff1a; 题解&#xff1a; #include <bits/stdc.h> using namespace std; using ll long long; const int N 105; const ll p 1e6 7; ll a[N], dp[N][N];int main() {int n, m; cin >> n >> m;for(int i 1; i < n; i)cin >> a[i…
阅读更多...
[Semi-笔记]Switching Temporary Teachers for Semi-Supervised Semantic Segmentation

[Semi-笔记]Switching Temporary Teachers for Semi-Supervised Semantic Segmentation

目录 概要创新一&#xff1a;Dual Temporary Teacher挑战&#xff1a;解决&#xff1a; 创新二&#xff1a;Implicit Consistency Learning&#xff08;隐式一致性学习&#xff09;挑战&#xff1a;解决&#xff1a; 实验结果小结论文地址代码地址 分享一篇2023年NeurIPS的文章…
阅读更多...
学浪课程提取工具blog

学浪课程提取工具blog

由于抖音的流行,带动了学浪的销售,有些人可能不知道学浪是什么,学浪其实就是抖音课堂的前身,既然学浪官方不提供下载选项,但是有需求就一定有解决需求的方案,这不,经过研究,终于研究出来了学浪下载工具 这款学浪下载工具有需要的自己下载下来,我已经打包好了 链接&#xff1a…
阅读更多...
软件项目的外包开发流程

软件项目的外包开发流程

软件项目的开发流程是一个系统化的过程&#xff0c;旨在确保软件产品能够高效、稳定地满足用户需求。在中国&#xff0c;软件产业的发展得到了国家的大力支持&#xff0c;众多软件企业遵循国际标准和最佳实践&#xff0c;推动了软件工程的进步。 以下是一般的软件项目开发流程&…
阅读更多...
Web API —— BOM 学习（完结）

Web API —— BOM 学习（完结）

目录 一、BOM 介绍 二、Window 对象 &#xff08;一&#xff09;基本介绍 &#xff08;二&#xff09;定时器 —— 延时函数 1.语法 2.清除时间函数 3.和 interval 间歇函数的区别 &#xff08;三&#xff09;JS 执行机制 1.介绍 2.同步任务 3.异步任务 4.执行过程…
阅读更多...
JetBrains全家桶激活，分享 WebStorm 2024 激活的方案

JetBrains全家桶激活，分享 WebStorm 2024 激活的方案

大家好&#xff0c;欢迎来到金榜探云手&#xff01; WebStorm公司简介 JetBrains 是一家专注于开发工具的软件公司&#xff0c;总部位于捷克。他们以提供强大的集成开发环境&#xff08;IDE&#xff09;而闻名&#xff0c;如 IntelliJ IDEA、PyCharm、和 WebStorm等。这些工具…
阅读更多...
Java SPI解读：揭秘服务提供接口的设计与应用

Java SPI解读：揭秘服务提供接口的设计与应用

一、什么是SPI&#xff1f; 在 Java 编程中&#xff0c;SPI&#xff08;Service Provider Interface&#xff09;是实现可插拔式应用的一种机制。它就像是应用程序的魔法盒&#xff0c;让你可以随时添加新的功能实现&#xff0c;而不需搞得一团糟。通过SPI&#xff0c;我们可以…
阅读更多...
汇春科技之MDT10F684

汇春科技之MDT10F684

目录 第一、时钟 第二&#xff0c;定时器Timer0 第三&#xff0c;pwm 汇春官网&#xff1a;汇春科技 (yspringtech.com) 汇春是麦肯的原厂&#xff0c;以下是两个论坛&#xff0c;其中都有关于麦肯单片机的学习论坛&#xff0c;可以参考学习&#xff0c;第一个叫英锐恩&…
阅读更多...
c++24.3.28函数值传递

c++24.3.28函数值传递

实践
阅读更多...
康耐视visionpro-CogAcqFifoTool工具详细说明

康耐视visionpro-CogAcqFifoTool工具详细说明

CogAcqFifoTool操作说明&#xff1a; ① 打开工具栏&#xff0c;双击或点击鼠标拖拽 添加CogAcqFifoTool ②.从图片采集设备/图像采集卡列表里选择对应的相机&#xff0c;视频格式选择图像格式。 Mono表示黑白图像&#xff0c;RGB表示彩色相机。点击初始化取相初始化相机。 ③…
阅读更多...
【OJ】动归练习三

【OJ】动归练习三

个人主页 &#xff1a; zxctscl 如有转载请先通知 题目 1. LCR166. 珠宝的最高价值1.1 分析1.2 代码 2. 931.下降路径最小和2.1 分析2.2 代码 3. 64.最小路径和3.1 分析3.2 代码 1. LCR166. 珠宝的最高价值 1.1 分析 状态表示 以[i][j]位置为结尾&#xff0c;表示到达[i][j]位置…
阅读更多...
最新文章

Copyright @ 2022~2023