【蓝桥杯】赛前练习

1. 排序

import os
import sysn=int(input())
data=list(map(int,input().split(" ")))
data.sort()
for d in data:print(d,end=" ")
print()
for d in data[::-1]:print(d,end=" ")

2. 走迷宫BFS

import os
import sys
from collections import dequen,m=map(int,input().split())
maze=[]
for _ in range(n):row=list(map(int,input().strip().split()))maze.append(row)
x1,y1,x2,y2=map(int,input().split())
x1 -= 1
y1 -= 1
x2 -= 1
y2 -= 1def bfs_maze(n,m,maze,x1,y1,x2,y2):directions=[(-1,0),(1,0),(0,-1),(0,1)]queue=deque()queue.append((x1,y1,0))visited=[[False for _ in range(m)] for _ in range(n)]visited[x1][y1]=Truewhile queue:x,y,step=queue.popleft()if x==x2 and y==y2:return stepfor dx,dy in directions:nx,ny=x+dx,y+dyif nx<0 or nx>=n or ny<0 or ny>=m:continueif maze[nx][ny]!=1 or visited[nx][ny]==True:continuevisited[nx][ny]=Truequeue.append((nx,ny,step+1))return -1print(bfs_maze(n,m,maze,x1,y1,x2,y2))

 优化后的代码

from collections import deque# 读取迷宫的行数和列数
n, m = map(int, input().split())
# 直接读取迷宫矩阵
maze = [list(map(int, input().split())) for _ in range(n)]
# 读取起点和终点坐标并调整为 0 索引
x1, y1, x2, y2 = [i - 1 for i in map(int, input().split())]def bfs_maze(n, m, maze, x1, y1, x2, y2):# 定义四个移动方向directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]# 初始化队列queue = deque([(x1, y1, 0)])# 初始化访问标记数组visited = [[False] * m for _ in range(n)]visited[x1][y1] = Truewhile queue:x, y, step = queue.popleft()# 若到达终点，返回步数if (x, y) == (x2, y2):return step# 遍历四个方向for dx, dy in directions:nx, ny = x + dx, y + dy# 检查新位置是否合法且未访问if 0 <= nx < n and 0 <= ny < m and maze[nx][ny] == 1 and not visited[nx][ny]:visited[nx][ny] = Truequeue.append((nx, ny, step + 1))# 未找到路径，返回 -1return -1# 调用函数并输出结果
print(bfs_maze(n, m, maze, x1, y1, x2, y2))

3. 01背包问题

import os
import sys# 从用户输入获取物品数量和背包容量
num_items, max_capacity = map(int, input().split())
# 存储每个物品的重量和价值
weights = []
values = []
# 循环获取每个物品的重量和价值
for _ in range(num_items):weight, value = map(int, input().split())weights.append(weight)values.append(value)# 创建一个二维数组 dp 用于动态规划，dp[i][w] 表示前 i 个物品在容量为 w 的背包中的最大价值
dp = [[0 for _ in range(max_capacity + 1)] for _ in range(num_items + 1)]
# 记录每个状态下选择的物品
choices = [[False for _