备战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 q
- if st[a_][b_][c_]:return
- q.append([a_,b_,c_])
- st[a_][b_][c_]=1
- def bfs():
- q.append([0,0,c])
- st[0][0][c]=1
- while 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(c+1):
- for b_ in range(b+1):
- 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]*(m+5)]
- for i in range(n):
- mp.append([0]+list(map(int,input().split())))
- dir = [(1,0),(-1,0),(0,1),(0,-1)]
- st = [[0]*(m+5) for _ in range(n+5)]
- def bfs():
- q = deque()
- q.append([1,1,0])
- st[1][1]=1
- while q:
- tx,ty,step = q.popleft()
- if tx==n and ty==m:
- print(step)
- return
- for x_,y_ in dir:
- nx,ny = tx+x_,ty+y_
- if nx<1 or nx>n or ny<1 or ny>m:continue
- if mp[nx][ny]==1 or st[nx][ny]:continue
- q.append( [nx,ny,step+1] )
- 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 = 0
- q.append( [s,idx,step] )
- ns = "".join(s)
- mp[ns]=1
- flag,res = 0,-1
- while q:
- ss,sidx,step = q.popleft()
- if "".join(ss)==norm:
- res = step
- break
- for i in dir:
- teps = ss.copy()
- nidx = sidx + i
- if nidx<1 or nidx>9:continue
- if (sidx==3 or sidx==6) and i==1:continue
- if (sidx==4 or sidx==7) and i==-1:continue
- teps[sidx],teps[nidx] = teps[nidx], teps[sidx]
- nteps = "".join(teps)
- if mp[nteps]:continue
- mp[nteps]=1
- q.append( [teps,nidx,step+1] )
- 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]*(n+5) for _ in range(n+5)]
- for i in range(n):
- mp.append(list(input()))
- def bfs(x,y):
- global res
- q = deque()
- flag = 0
- q.append([x,y])
- st[x][y]=1
- while q:
- tx,ty = q.popleft()
- for a,b in [[1,0],[-1,0],[0,1],[0,-1]]:
- nx,ny = tx+a,ty+b
- if nx<0 or nx>=n or ny<0 or ny>=n:continue
- if mp[nx][ny]=='.' or st[nx][ny]:continue
- st[nx][ny]=1
- if mp[nx+1][ny]==mp[nx-1][ny]==mp[nx][ny+1]==mp[nx][ny-1]=='#':flag=1
- q.append([nx,ny])
- if flag:res+=1
- cnt = 0
- for i in range(n):
- for j in range(n):
- if mp[i][j]=='#' and st[i][j]==0:
- cnt +=1
- bfs(i,j)
- print(cnt-res)
【题目描述】
在一个 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]=1
- flag,res = 0,-1
- while q:
- ss,sidx,step = q.popleft()
- if "".join(ss)==norm:
- flag = 1
- res = step
- break
- for i in range(4):
- teps = ss.copy()
- nidx = sidx + dir[i]
- if nidx<1 or nidx>9:continue
- if (sidx==3 or sidx==6) and dir[i]==1:continue
- if (sidx==4 or sidx==7) and dir[i]==-1:continue
- teps[sidx],teps[nidx] = teps[nidx], teps[sidx]
- nteps = "".join(teps)
- if mp[nteps]:continue
- mp[nteps]=1
- q.append( [teps,nidx,step+fx[i]] )
- if flag:print(res)
- else:print('unsolvable')
- bfs()