不管遇到多大的困難，我們都要堅持下去。每一次挫折都是我們成長的機會，每一次失敗都是我們前進的動力。路漫漫其修遠兮，吾將上下而求索。只有不斷努力奮斗，才能追逐到自己的夢想。不要害怕失敗，害怕的是不敢去嘗試。只有敢于面對挑戰，才能收獲成功的喜悅。我們要相信自己的能力，堅信自己可以做到。生活可以很艱難，但我們要有勇氣去面對，有決心去戰勝它。相信自己，努力拼搏，我們一定能夠創造屬于自己的輝煌！

藍橋杯官網https://dasai.lanqiao.cn/

刷題https://leetcode.cn/

目錄

題目1：迷宮最短路徑問題

題目2：最長公共子序列（LCS）

解答過程和代碼

題目1：迷宮最短路徑問題

解答過程：

Python代碼實現：

題目2：最長公共子序列（LCS）

解答過程：

Python代碼實現：

---

藍橋杯全國軟件和信息技術專業人才大賽是中國知名的編程競賽之一，B組通常面向本科二年級及以下的學生。為了提供兩個有意義且重要的題目，我會根據歷年的比賽特點以及考察的重點技能來設計。以下是兩個具有代表性的題目示例：

題目1：迷宮最短路徑問題

背景描述： 在一個由方格組成的矩形迷宮中，每個方格可能是空地（用0表示）或墻壁（用1表示）。給定一個起點和一個終點，要求找到從起點到終點的最短路徑，并輸出該路徑的長度。如果不存在這樣的路徑，則輸出-1。

輸入格式： 第一行包含兩個整數m和n (1 <= m, n <= 100)，分別表示迷宮的行數和列數。 接下來m行，每行包含n個字符，組成迷宮的地圖，其中S表示起點，E表示終點，0表示空地，1表示墻壁。 保證地圖中只有一個起點和一個終點。

輸出格式： 輸出一個整數，表示從起點到終點的最短路徑長度。如果不存在這樣的路徑，則輸出-1。

樣例輸入：

5 5
S0101
01010
00000
10110
1000E

樣例輸出：

8

解題思路： 這個問題可以使用廣度優先搜索算法（BFS）來解決。BFS是一種適合用于尋找最短路徑的圖遍歷算法。具體步驟如下：

1. 將起點加入隊列，并標記為已訪問。
2. 每次從隊列中取出一個節點，檢查其四個方向上的鄰居節點是否是終點、空地且未被訪問過。如果是，則將這些節點加入隊列并標記為已訪問，同時記錄步數。
3. 如果在某一步找到了終點，則返回當前步數；否則繼續遍歷直到隊列為空。
4. 如果遍歷結束仍未找到終點，則說明沒有路徑可達，返回-1。

難度： 中等

知識點： 圖論、廣度優先搜索（BFS）、隊列操作

---

題目2：最長公共子序列（LCS）

背景描述： 給定兩個字符串s1和s2，求它們的最長公共子序列（Longest Common Subsequence, LCS）。子序列是指可以從原序列中刪除若干元素而不改變剩余元素順序得到的新序列。注意，這里的“公共”意味著這個子序列同時出現在兩個字符串中。

輸入格式： 第一行包含一個字符串s1。 第二行包含一個字符串s2。 字符串僅包含小寫字母，長度不超過1000。

輸出格式： 輸出一個整數，表示最長公共子序列的長度。

樣例輸入：

abcde
ace

樣例輸出：

3

解題思路： 這個問題可以通過動態規劃（Dynamic Programming, DP）來高效解決。我們定義一個二維數組dp[i][j]，表示s1前i個字符與s2前j個字符之間的最長公共子序列長度。狀態轉移方程如下：

• 如果s1[i] == s2[j]，那么dp[i][j] = dp[i-1][j-1] + 1；
• 否則，dp[i][j] = max(dp[i-1][j], dp[i][j-1])。

最終答案就是dp[len(s1)][len(s2)]，其中len()函數返回字符串的長度。

難度： 中等偏難

知識點： 動態規劃（DP）、字符串處理

這兩個題目不僅涵蓋了基本的數據結構和算法知識，而且對于培養學生的邏輯思維能力和解決問題的能力也非常有幫助。

解答過程和代碼

題目1：迷宮最短路徑問題

解答過程：

廣度優先搜索（BFS）算法 是解決此類問題的最佳選擇，因為它可以保證找到從起點到終點的最短路徑。我們使用隊列來存儲待訪問的節點，并且記錄每個節點到達時的距離。

步驟：

1. 初始化：
   • 創建一個二維數組?visited?來標記哪些位置已經被訪問。
   • 初始化隊列，將起點加入隊列，并設置其距離為0。
2. 遍歷：
   • 從隊列中取出一個節點，檢查它是否是終點。
   • 如果不是終點，則檢查它的四個方向（上、下、左、右），對于每個方向：
     • 如果新位置在迷宮范圍內且未被訪問過，并且是空地（0?或?E），則將其加入隊列，并標記為已訪問，同時更新距離。
3. 結束條件：
   • 如果在某一步找到了終點，則返回當前步數。
   • 如果遍歷結束仍未找到終點，則返回-1表示沒有路徑可達。

Python代碼實現：

from collections import dequedef shortest_path(maze):m, n = len(maze), len(maze[0])directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]  # 上下左右四個方向# 找到起點和終點的位置start, end = None, Nonefor i in range(m):for j in range(n):if maze[i][j] == 'S':start = (i, j)elif maze[i][j] == 'E':end = (i, j)if not start or not end:return -1# BFSqueue = deque([(start[0], start[1], 0)])  # (x, y, distance)visited = set()visited.add(start)while queue:x, y, dist = queue.popleft()if (x, y) == end:return distfor dx, dy in directions:nx, ny = x + dx, y + dyif 0 <= nx < m and 0 <= ny < n and (nx, ny) not in visited and maze[nx][ny] in ('0', 'E'):queue.append((nx, ny, dist + 1))visited.add((nx, ny))return -1# 示例輸入
maze_input = ["S0101","01010","00000","10110","1000E"
]# 將輸入轉換成列表形式
maze = [list(row) for row in maze_input]# 調用函數并打印結果
print(shortest_path(maze))  # 輸出: 8

---

題目2：最長公共子序列（LCS）

解答過程：

動態規劃（DP）算法 是求解最長公共子序列問題的有效方法。通過構建一個二維表 dp，其中 dp[i][j] 表示字符串 s1 的前 i 個字符與 s2 的前 j 個字符之間的最長公共子序列長度。

狀態轉移方程：

• 如果?s1[i-1] == s2[j-1]，那么?dp[i][j] = dp[i-1][j-1] + 1；
• 否則，dp[i][j] = max(dp[i-1][j], dp[i][j-1])。

最終答案就是 dp[len(s1)][len(s2)]。

Python代碼實現：

def longest_common_subsequence(s1, s2):m, n = len(s1), len(s2)# 創建dp表格，額外一行一列用于處理邊界情況dp = [[0] * (n + 1) for _ in range(m + 1)]# 填充dp表格for i in range(1, m + 1):for j in range(1, n + 1):if s1[i - 1] == s2[j - 1]:dp[i][j] = dp[i - 1][j - 1] + 1else:dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])return dp[m][n]# 示例輸入
s1 = "abcde"
s2 = "ace"# 調用函數并打印結果
print(longest_common_subsequence(s1, s2))  # 輸出: 3

這兩個題目不僅涵蓋了基本的數據結構和算法知識，而且對于培養學生的邏輯思維能力和解決問題的能力也非常有幫助。