网站开发类合同范本,长春建站程序,网站如何上传数据库,wordpress 安装新主题备战2024年蓝桥杯 -- 每日一题 Python大学A组 试题一#xff1a;母亲的奶牛 试题二#xff1a;走迷宫 试题三#xff1a;八数码1 试题四#xff1a;全球变暖 试题五#xff1a;八数码2 试题一#xff1a;母亲的奶牛
【题目描述】 农夫约…备战2024年蓝桥杯 -- 每日一题 Python大学A组 试题一母亲的奶牛 试题二走迷宫 试题三八数码1 试题四全球变暖 试题五八数码2 试题一母亲的奶牛
【题目描述】 农夫约翰有三个容量分别为 A,B,C 升的挤奶桶。最开始桶 A 和桶 B 都是空的而桶 C 里装满了牛奶。有时约翰会将牛奶从一个桶倒到另一个桶中直到被倒入牛奶的桶满了或者倒出牛奶的桶空了为止。这一过程中间不能有任何停顿并且不会有任何牛奶的浪费。请你编写一个程序判断当 A 桶是空的时候C桶中可能包含多少升牛奶找出所有的可能情况。
【输入格式】 共一行包含三个整数 A,B,C。
【输出格式】 共一行包含若干个整数表示 C 桶中牛奶存量的所有可能情况请将这些数字按升序排列。
【数据范围】 1≤A,B,C≤20
【输入样例】
8 9 10
【输出样例】
1 2 8 9 10 【解题思路】 BFS简答模拟一下倒牛奶的过程。
【Python程序代码】
from collections import *
a,b,c map(int,input().split())
n 22
st [[[0 for _ in range(n)] for _ in range(n)] for _ in range(n)]q deque()
def ins(a_,b_,c_):global qif st[a_][b_][c_]:returnq.append([a_,b_,c_])st[a_][b_][c_]1
def bfs():q.append([0,0,c])st[0][0][c]1while q:a_,b_,c_ q.popleft()ins( a_-min(a_,b-b_) , b_min(a_,b-b_) , c_ )ins( a_-min(a_,c-c_) , b_ , c_min(a_,c-c_) )ins( a_min(b_,a-a_) , b_-min(b_,a-a_) , c_ )ins( a_ , b_-min(b_,c-c_) , c_min(b_,c-c_) )ins( a_min(c_,a-a_) , b_ , c_-min(c_,a-a_) )ins( a_ , b_min(c_,b-b_) , c_-min(c_,b-b_) )
bfs()
for c_ in range(c1):for b_ in range(b1):if st[0][b_][c_]:print(c_,end )break试题二走迷宫
【题目描述】 给定一个 n×m 的二维整数数组用来表示一个迷宫数组中只包含 0 或 1其中 0 表示可以走的路1 表示不可通过的墙壁。最初有一个人位于左上角 (1,1)处已知该人每次可以向上、下、左、右任意一个方向移动一个位置。请问该人从左上角移动至右下角 (n,m)处至少需要移动多少次。数据保证 (1,1) 处和 (n,m) 处的数字为 0且一定至少存在一条通路。
【输入格式】 第一行包含两个整数 n 和 m。 接下来 n行每行包含 m 个整数0 或 1表示完整的二维数组迷宫。
【输出格式】 输出一个整数表示从左上角移动至右下角的最少移动次数。
【数据范围】 1≤n,m≤100
【输入样例】
5 5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
【输出样例】
8 【解题思路】 BFS的典中典。
【Python程序代码】
from collections import *
n,m map(int,input().split())
mp [[0]*(m5)]
for i in range(n):mp.append([0]list(map(int,input().split())))
dir [(1,0),(-1,0),(0,1),(0,-1)]
st [[0]*(m5) for _ in range(n5)]
def bfs():q deque()q.append([1,1,0])st[1][1]1while q:tx,ty,step q.popleft()if txn and tym:print(step)returnfor x_,y_ in dir:nx,ny txx_,tyy_if nx1 or nxn or ny1 or nym:continueif mp[nx][ny]1 or st[nx][ny]:continueq.append( [nx,ny,step1] )st[nx][ny]1
bfs() 试题三八数码
【题目描述】 在一个 3×3 的网格中1∼8这 8 个数字和一个 x 恰好不重不漏地分布在这 3×3的网格中。
例如
1 2 3
x 4 6
7 5 8 在游戏过程中可以把 x 与其上、下、左、右四个方向之一的数字交换如果存在。我们的目的是通过交换使得网格变为如下排列称为正确排列
1 2 3
4 5 6
7 8 x 例如示例中图形就可以通过让 x 先后与右、下、右三个方向的数字交换成功得到正确排列。交换过程如下
1 2 3 1 2 3 1 2 3 1 2 3
x 4 6 4 x 6 4 5 6 4 5 6
7 5 8 7 5 8 7 x 8 7 8 x 把 x 与上下左右方向数字交换的行动记录为 u、d、l、r。现在给你一个初始网格请你通过最少的移动次数得到正确排列。
【输入格式】 输入占一行将 3×3 的初始网格描绘出来。例如如果初始网格如下所示
1 2 3
x 4 6
7 5 8 则输入为1 2 3 x 4 6 7 5 8
【输出格式】 输出占一行包含一个整数表示最少交换次数。 如果不存在解决方案则输出 −1。
【输入样例】
2 3 4 1 5 x 7 6 8
【输出样例】
19
【解题思路】 简答题用BFS遍历查找即可。
【Python程序代码】
from collections import *
pd [0,1,2,3,4,5,6,7,8,x]
norm .join(pd)
dir [1,-1,3,-3]
s [0] list(map(str,input().split()))
idx s.index(x)
mp defaultdict(int)
def bfs():q deque()step 0q.append( [s,idx,step] )ns .join(s)mp[ns]1flag,res 0,-1while q:ss,sidx,step q.popleft()if .join(ss)norm:res stepbreakfor i in dir:teps ss.copy()nidx sidx iif nidx1 or nidx9:continueif (sidx3 or sidx6) and i1:continueif (sidx4 or sidx7) and i-1:continueteps[sidx],teps[nidx] teps[nidx], teps[sidx]nteps .join(teps)if mp[nteps]:continuemp[nteps]1q.append( [teps,nidx,step1] )print(res)
bfs()试题四全球变暖
【题目描述】 你有一张某海域 N×N像素的照片”.”表示海洋、”#”表示陆地如下所示
.......
.##....
.##....
....##.
..####.
...###.
....... 其中”上下左右”四个方向上连在一起的一片陆地组成一座岛屿例如上图就有 22 座岛屿。由于全球变暖导致了海面上升科学家预测未来几十年岛屿边缘一个像素的范围会被海水淹没。具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋)它就会被淹没。例如上图中的海域未来会变成如下样子
.......
.......
.......
.......
....#..
.......
....... 请你计算依照科学家的预测照片中有多少岛屿会被完全淹没。
【输入格式】 第一行包含一个整数N。 以下 N 行 N 列包含一个由字符”#”和”.”构成的 N×N字符矩阵代表一张海域照片”#”表示陆地”.”表示海洋。 照片保证第 1行、第 1 列、第 N 行、第 N 列的像素都是海洋。
【输出格式】 一个整数表示答案。
【数据范围】 1≤N≤1000
【输入样例】
7
.......
.##....
.##....
....##.
..####.
...###.
.......
【输出样例】
1
【解题思路】 简答题用BFS找一遍就可以。
【Python程序代码】
from collections import *
n int(input())
mp,res [],0
st [[0]*(n5) for _ in range(n5)]
for i in range(n):mp.append(list(input()))
def bfs(x,y):global resq deque()flag 0q.append([x,y])st[x][y]1while q:tx,ty q.popleft()for a,b in [[1,0],[-1,0],[0,1],[0,-1]]:nx,ny txa,tybif nx0 or nxn or ny0 or nyn:continueif mp[nx][ny]. or st[nx][ny]:continuest[nx][ny]1if mp[nx1][ny]mp[nx-1][ny]mp[nx][ny1]mp[nx][ny-1]#:flag1q.append([nx,ny])if flag:res1
cnt 0
for i in range(n):for j in range(n):if mp[i][j]# and st[i][j]0:cnt 1bfs(i,j)
print(cnt-res) 试题五八数码2
【题目描述】 在一个 3×3 的网格中1∼8这 8 个数字和一个 x 恰好不重不漏地分布在这 3×3的网格中。
例如
1 2 3
x 4 6
7 5 8 在游戏过程中可以把 x 与其上、下、左、右四个方向之一的数字交换如果存在。我们的目的是通过交换使得网格变为如下排列称为正确排列
1 2 3
4 5 6
7 8 x 例如示例中图形就可以通过让 x 先后与右、下、右三个方向的数字交换成功得到正确排列。交换过程如下
1 2 3 1 2 3 1 2 3 1 2 3
x 4 6 4 x 6 4 5 6 4 5 6
7 5 8 7 5 8 7 x 8 7 8 x 把 x 与上下左右方向数字交换的行动记录为 u、d、l、r。现在给你一个初始网格请你通过最少的移动次数得到正确排列。
【输入格式】 输入占一行将 3×3 的初始网格描绘出来。例如如果初始网格如下所示
1 2 3
x 4 6
7 5 8 则输入为1 2 3 x 4 6 7 5 8
【输出格式】 输出占一行包含一个字符串表示得到正确排列的完整行动记录。 如果答案不唯一输出任意一种合法方案即可。 如果不存在解决方案则输出 unsolvable。
【输入样例】
2 3 4 1 5 x 7 6 8
【输出样例】
ullddrurdllurdruldr
【解题思路】 简答题在前面八数码1的基础上改一下step就可以了。
【Python程序代码】
from collections import *
pd [0,1,2,3,4,5,6,7,8,x]
norm .join(pd)
dir [1,-1,3,-3]
fx [r,l,d,u]
s [0] list(map(str,input().split()))
idx s.index(x)
mp defaultdict(int)
def bfs():q deque()step q.append( [s,idx,step] )ns .join(s)mp[ns]1flag,res 0,-1while q:ss,sidx,step q.popleft()if .join(ss)norm:flag 1res stepbreakfor i in range(4):teps ss.copy()nidx sidx dir[i]if nidx1 or nidx9:continueif (sidx3 or sidx6) and dir[i]1:continueif (sidx4 or sidx7) and dir[i]-1:continueteps[sidx],teps[nidx] teps[nidx], teps[sidx]nteps .join(teps)if mp[nteps]:continuemp[nteps]1q.append( [teps,nidx,stepfx[i]] )if flag:print(res)else:print(unsolvable)
bfs()
