当前位置：首页 > news >正文

蓝桥杯之暴力回溯

news 2025/3/25 19:06:26

文章目录

数字接龙
小u的最大连续移动次数问题

在蓝桥杯中，十分喜欢考察对于网格的回溯的问题，对于这类的问题，常常会使用到这个DFS和BFS进行考察，不过无论怎么考察，都只是会在最基础的模本的基础上，根据这个题目的条件：
- 增加递归传递的参数
- 增加条件转移的时候的条件的判断
- 考察对于终止状态的设置，答案的存储与更新

数字接龙

在这里插入图片描述

查看数据范围，适合直接进行暴露的DFS搜索
题目的条件有点多，我们逐一进行分析：
- 需要记录哪些信息？
  - 当前位置的数字，当前的坐标，当前访问过的方格的数目
  - 为了保证每一个格子只能访问过一次，所以得使用visited数组
  - 移动的方向的，得使用一个二维数组step来记录，得逐一步伐的顺序与对应的方位顺序是一致的
  - 对于答案的记录，考虑使用这个字符来记录，最后再合并就好了
  - 对于交叉的判断的综合考虑？

代码版本1，不考虑这个交叉的问题

import os
import sys# sys.setrecursionlimit(10 ** 6)
# 请在此输入您的代码N,K = map(int,input().split())
e = []
# 存储图
for _ in range(N):tmp = list(map(int,input().split()))e.append(tmp)# 状态转移的路径,左，右，上，下，左上角，右上角，左下角，右下角
# 转移还得按照这个顺序
#step = [[0,-1],[0,1],[-1,0],[1,0],[-1,-1],[-1,1],[1,-1],[1,1]]
step = [[-1,0],[-1,1],[0,1],[1,1],[1,0],[1,-1],[0,-1],[-1,-1]]ans = []
path = []visited = [[False]*N for _ in range(N)]# 开始深度搜索,每一步的时候，判断下面是否是0,还是i+1,还得判断是否都走过了每一个位置
def dfs(i,x,y,cursum):# 终止状态if x == N-1 and y == N-1 and cursum == N*N:ans.append(int(''.join(path)))# 如何转移？for j in range(8):nx,ny = x+step[j][0],y+step[j][1]if 0<= nx < N and 0<= ny < N and not visited[nx][ny] and (e[nx][ny] == 0 or e[nx][ny] == i + 1):# 还是得存储这个字符形式visited[nx][ny] = Truepath.append(str(j))dfs(e[nx][ny],nx,ny,cursum+1)path.pop()visited[nx][ny] = Falsevisited[0][0] = True
dfs(e[0][0],0,0,1)
if ans:print(min(ans))
else:print(-1)

测试样例的通过的情况：

在这里插入图片描述

增加了对于交叉的判断


import os
import sys# sys.setrecursionlimit(10 ** 6)
# 请在此输入您的代码N,K = map(int,input().split())
e = []
# 存储图
for _ in range(N):tmp = list(map(int,input().split()))e.append(tmp)# 状态转移的路径,左，右，上，下，左上角，右上角，左下角，右下角
# 转移还得按照这个顺序
#step = [[0,-1],[0,1],[-1,0],[1,0],[-1,-1],[-1,1],[1,-1],[1,1]]
step = [[-1,0],[-1,1],[0,1],[1,1],[1,0],[1,-1],[0,-1],[-1,-1]]ans = []
path = []visited = [[False]*N for _ in range(N)]# 开始深度搜索,每一步的时候，判断下面是否是0,还是i+1,还得判断是否都走过了每一个位置
def dfs(i,x,y,cursum):# 终止状态if x == N-1 and y == N-1 and cursum == N*N:ans.append(int(''.join(path)))# 如何转移？for j in range(8):nx,ny = x+step[j][0],y+step[j][1]if 0<= nx < N and 0<= ny < N and not visited[nx][ny] and (e[nx][ny] == 0 or e[nx][ny] == i + 1):if j == 1 and 0<= x-1 and y+1 < N:if visited[x][y+1] and visited[x-1][y]:continueif j == 3 and x+1 < N and y+1 < N:if visited[x][y+1] and visited[x+1][y]:continueif j == 5 and x+1 < N and 0<= y-1:if visited[x][y-1] and visited[x+1][y]:continueif j == 7 and 0<= y-1 and 0<= x-1:if visited[x][y-1] and visited[x-1][y]:continue# 还是得存储这个字符形式visited[nx][ny] = Truepath.append(str(j))dfs(e[nx][ny],nx,ny,cursum+1)path.pop()visited[nx][ny] = Falsevisited[0][0] = True
dfs(e[0][0],0,0,1)
if ans:print(min(ans))
else:print(-1)

样例通过情况

在这里插入图片描述

改进这个交叉判断，上面的判断其实是不合理的，因为如果左右两边的位置都被访问过的话，并不确定对应的对角线是存在线的,正确的做法就是使用多一个数组记录当前位置的下一步是什么，如果左右位置存在对角线，那么就不能通过


import os
import sys# sys.setrecursionlimit(10 ** 6)
# 请在此输入您的代码N,K = map(int,input().split())
e = []
# 存储图
for _ in range(N):tmp = list(map(int,input().split()))e.append(tmp)# 状态转移的路径,左，右，上，下，左上角，右上角，左下角，右下角
# 转移还得按照这个顺序
#step = [[0,-1],[0,1],[-1,0],[1,0],[-1,-1],[-1,1],[1,-1],[1,1]]
step = [[-1,0],[-1,1],[0,1],[1,1],[1,0],[1,-1],[0,-1],[-1,-1]]ans = []
path = []visited = [[False]*N for _ in range(N)]
nextstep = [[-1]*N for _ in range(N)]# 开始深度搜索,每一步的时候，判断下面是否是0,还是i+1,还得判断是否都走过了每一个位置
def dfs(i,x,y,cursum):# 终止状态if x == N-1 and y == N-1 and cursum == N*N:if not ans:ans.append(int(''.join(path)))return # 如何转移？for j in range(8):nx,ny = x+step[j][0],y+step[j][1]if 0<= nx < N and 0<= ny < N and not visited[nx][ny] and (e[nx][ny] == 0 or e[nx][ny] == i + 1):if j == 1 and (nextstep[nx][ny-1] == 3 or nextstep[nx-1][ny] == 7): continueif j == 3 and (nextstep[nx-1][ny] == 5 or nextstep[nx][ny-1] == 1): continueif j == 5 and (nextstep[nx-1][ny] == 3 or nextstep[nx][ny+1] == 7): continueif j == 7 and (nextstep[nx+1][ny] == 1 or nextstep[nx][ny+1] == 5): continuenextstep[x][y] = j# 还是得存储这个字符形式visited[nx][ny] = Truepath.append(str(j))dfs(e[nx][ny],nx,ny,cursum+1)if ans:return path.pop()visited[nx][ny] = Falsenextstep[x][y] = -1visited[0][0] = True
dfs(e[0][0],0,0,1)
if ans:print(min(ans))
else:print(-1)

小u的最大连续移动次数问题

在这里插入图片描述

直接暴力进行求解
这个问题的难点在于这个没有明确的终止状态，所以考虑使用一个全局的变量进行动态的更新，直接都不返回值
需要记录的信息：
- 当前的位置x,y,当前的步数step,上一个状态是上坡还是下坡flag

def solution(m: int, n: int, a: list) -> int:# 先写一个dfs模版,后面再每一个点都进行调用sstep = [[0,-1],[0,1],[-1,0],[1,0]]visited = [[False]*n for _ in range(m)]ans = 0# 还得增加一个变量记录上次是上坡还是下坡,flag = 1表示上，-1表示下def dfs(x,y,step,flag):nonlocal ansans = max(ans,step)for s in sstep:nx,ny = x+s[0],y+s[1]if 0<= nx < m and 0<= ny < n and not visited[nx][ny]:if flag == -1 and a[nx][ny] > a[x][y]:visited[nx][ny] = Truedfs(nx,ny,step+1,1)visited[nx][ny] = Falseif flag == 1 and a[nx][ny] < a[x][y]:visited[nx][ny] = Truedfs(nx,ny,step+1,-1)visited[nx][ny] = Falseans = 0for i in range(m):for j in range(n):visited[i][j] = Truedfs(i,j,0,1)dfs(i,j,0,-1)visited[i][j] = Falsereturn ans