• 在藍橋杯中，十分喜歡考察對于網格的回溯的問題，對于這類的問題，常常會使用到這個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的最大連續移動次數問題

小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

迷宮

迷宮

• 求解的是最短距離的問題，所以首先得想到使用這個BFS進行求解
• 由于求解的是隨機起點到終點的距離，所以我們直接逆向思考，直接從終點進行遍歷，當棧為空的時候，就說明已經遍歷完全部的位置了

from collections import deque, defaultdictn, 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 - 1change[(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)]  # 使用二維數組記錄步數，初始值為 -1visited[start][end] = 0step = [[0, -1], [0, 1], [-1, 0], [1, 0]]while queue:s, e = queue.popleft()# 訪問鄰居for dx, dy in step:nx, ny = s + dx, e + dyif 0 <= nx < n and 0 <= ny < n and visited[nx][ny] == -1:visited[nx][ny] = visited[s][e] + 1queue.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] + 1queue.append((nx, ny))# 計算平均步數total = 0for 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}")