(蓝桥杯)DFS+BFS算法题目-python

DFS

1.排列数字

dfs和递归差不多，具体图示如下图：

N=10
path=[0]*N
state=[False]*N
def dfs(u):if u==n:for i in range(n):print(path[i],end=' ')print()for i in range(n):if state[i]==False:path[u]=i+1 state[i]=Truedfs(u+1)   #处理下一个位置path[u]=0  #恢复现场state[i]=False 
n=int(input()) #输入有n个数
dfs(0) #从第0个位置开始处理       

2.n皇后问题

.Q..
...Q
Q...
..Q...Q.
Q...
...Q
.Q..

def dfs(x,y,queue):if y==n:x,y=x+1,0#分支：放皇后if x==n:if queue==n:for i in range(n):for j in range(n):print(chessboard[i][j],end='')print()print()return #如果皇后没放完，说明此种摆放不行if not row[x] and not col[y] and not dg[x+y] and not udg[y-x+n]:chessboard[x][y]='Q'row[x],col[y],dg[x+y],udg[y-x+n]=1,1,1,1dfs(x,y+1,queue+1) #处理下一个皇后和下一个位置row[x],col[y],dg[x+y],udg[y-x+n],chessboard[x][y]=0,0,0,0,'.'#分支：不放dfs(x,y+1,queue) #该位置不能放皇后，则看下一个位置可以不
if __name__=='__main__':N=10 n=int(input())chessboard=[['.' for _ in range(N)] for _ in range(N)]row,col,dg,udg=[0]*N,[0]*N,[0]*2*N,[0]*2*Ndfs(0,0,0) #从第0行第0列，第0个皇后开始处理

BFS

走迷宫

输入样例：
5 5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
输出样例：
8

def bfs():#上下，左右移动dx=[-1,0,1,0] dy=[0,1,0,-1] queue=[(0,0)] #从左上角开始trace[0][0]=0while queue:x,y=queue.pop(0)if (x,y)==(n-1,m-1): #到达右下角return trace[x][y]for i in range(4): #在上下左右移动a=x+dx[i]b=y+dy[i]if 0<=a<n and 0<=b<m and graph[a][b]!=1 and trace[a][b]==-1: #没有走过，并且不是墙queue.append((a,b)) #这个位置可以走，并加入队列处理trace[a][b]=trace[x][y]+1 #该位置到原点的距离
N=101
n,m=map(int,input().split())
graph=[[0]*N for _ in range(N)] #迷宫地图初始化
trace=[[-1]*N for _ in range(N)] #行走轨迹
for i in range(n):graph[i][0:m]=list(map(int,input().split())) #迷宫建图
print(bfs()) #进行宽度优先搜索

青蛙跳杯子

x=input()
y=input()
move=[1,-1,2,-2,3,-3] #记录所有运动方式
aset={x} 
def bfs():Q=[(x,0)] #队列中放入初始队列，以及初始步数while Q: #依次出队，对每个状态进行处理old=Q.pop(0)for i in move:a=list(old[0])b=old[1]c=a.index('*') #记录*所在的下标d=c+i #与*要交换元素的下标if 0<=d<len(x):a[c]=a[d]a[d]='*'e=''.join(a)b+=1 #进行一部操作if e==y:print(b)return if e not in aset: #如果此时变换的序列之前没有出现aset.add(e)Q.append((e,b)) #变换后的序列和更新的步数入队。
bfs()