蓝桥杯 之 暴力回溯
文章目录
- 数字接龙
- 小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] = True
path.append(str(j))
dfs(e[nx][ny],nx,ny,cursum+1)
path.pop()
visited[nx][ny] = False
visited[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]:
continue
if j == 3 and x+1 < N and y+1 < N:
if visited[x][y+1] and visited[x+1][y]:
continue
if j == 5 and x+1 < N and 0<= y-1:
if visited[x][y-1] and visited[x+1][y]:
continue
if j == 7 and 0<= y-1 and 0<= x-1:
if visited[x][y-1] and visited[x-1][y]:
continue
# 还是得存储这个字符形式
visited[nx][ny] = True
path.append(str(j))
dfs(e[nx][ny],nx,ny,cursum+1)
path.pop()
visited[nx][ny] = False
visited[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): continue
if j == 3 and (nextstep[nx-1][ny] == 5 or nextstep[nx][ny-1] == 1): continue
if j == 5 and (nextstep[nx-1][ny] == 3 or nextstep[nx][ny+1] == 7): continue
if j == 7 and (nextstep[nx+1][ny] == 1 or nextstep[nx][ny+1] == 5): continue
nextstep[x][y] = j
# 还是得存储这个字符形式
visited[nx][ny] = True
path.append(str(j))
dfs(e[nx][ny],nx,ny,cursum+1)
if ans:
return
path.pop()
visited[nx][ny] = False
nextstep[x][y] = -1
visited[0][0] = True
dfs(e[0][0],0,0,1)
if ans:
print(min(ans))
else:
print(-1)
小u的最大连续移动次数问题
小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 ans
ans = 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] = True
dfs(nx,ny,step+1,1)
visited[nx][ny] = False
if flag == 1 and a[nx][ny] < a[x][y]:
visited[nx][ny] = True
dfs(nx,ny,step+1,-1)
visited[nx][ny] = False
ans = 0
for i in range(m):
for j in range(n):
visited[i][j] = True
dfs(i,j,0,1)
dfs(i,j,0,-1)
visited[i][j] = False
return ans
迷宫
迷宫
- 求解的是最短距离的问题，所以首先得想到使用这个
BFS进行求解 - 由于求解的是随机起点到终点的距离，所以我们直接
逆向思考，直接从终点进行遍历，当栈为空的时候，就说明已经遍历完全部的位置了
from collections import deque, defaultdict
n, m = map(int, input().split())
change = defaultdict(list)
for _ in range(m):
x1, y1, x2, y2 = map(int, input().split())
x1, y1, x2, y2 = x1 - 1, y1 - 1, x2 - 1, y2 - 1
change[(x1, y1)].append((x2, y2))
change[(x2, y2)].append((x1, y1))
def bfs(start, end):
queue = deque([(start, end)])
visited = [[-1] * n for _ in range(n)] # 使用二维数组记录步数，初始值为 -1
visited[start][end] = 0
step = [[0, -1], [0, 1], [-1, 0], [1, 0]]
while queue:
s, e = queue.popleft()
# 访问邻居
for dx, dy in step:
nx, ny = s + dx, e + dy
if 0 <= nx < n and 0 <= ny < n and visited[nx][ny] == -1:
visited[nx][ny] = visited[s][e] + 1
queue.append((nx, ny))
# 走传送门
if (s, e) in change:
for nx, ny in change[(s, e)]:
if visited[nx][ny] == -1:
visited[nx][ny] = visited[s][e] + 1
queue.append((nx, ny))
# 计算平均步数
total = 0
for x in range(n):
for y in range(n):
total += visited[x][y]
return total / (n * n)
print(f"{bfs(n - 1, n - 1):.2f}")