備戰(zhàn)2024年藍橋杯?-- 每日一題
Python大學A組

????????試題一：母親的奶牛
????????試題二：走迷宮
????????試題三：八數(shù)碼1
? ? ? ??試題四：全球變暖
????????試題五：八數(shù)碼2

---

試題一：母親的奶牛

【題目描述】

????????農(nóng)夫約翰有三個容量分別為?A,B,C 升的擠奶桶。最開始桶?A 和桶?B 都是空的，而桶?C 里裝滿了牛奶。有時，約翰會將牛奶從一個桶倒到另一個桶中，直到被倒入牛奶的桶滿了或者倒出牛奶的桶空了為止。這一過程中間不能有任何停頓，并且不會有任何牛奶的浪費。請你編寫一個程序判斷，當?A 桶是空的時候，C桶中可能包含多少升牛奶，找出所有的可能情況。

【輸入格式】

????????共一行，包含三個整數(shù)?A,B,C。

【輸出格式】

????????共一行，包含若干個整數(shù)，表示?C 桶中牛奶存量的所有可能情況，請將這些數(shù)字按升序排列。

【數(shù)據(jù)范圍】

????????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(c+1):for b_ in range(b+1):if st[0][b_][c_]:print(c_,end=' ')break

---

?試題二：走迷宮

【題目描述】

????????給定一個?n×m 的二維整數(shù)數(shù)組，用來表示一個迷宮，數(shù)組中只包含?0 或?1，其中?0 表示可以走的路，1 表示不可通過的墻壁。最初，有一個人位于左上角?(1,1)處，已知該人每次可以向上、下、左、右任意一個方向移動一個位置。請問，該人從左上角移動至右下角?(n,m)處，至少需要移動多少次。數(shù)據(jù)保證?(1,1) 處和?(n,m)?處的數(shù)字為?0，且一定至少存在一條通路。

【輸入格式】

????????第一行包含兩個整數(shù)?n?和?m。

????????接下來?n行，每行包含?m?個整數(shù)（0?或?1），表示完整的二維數(shù)組迷宮。

【輸出格式】

????????輸出一個整數(shù)，表示從左上角移動至右下角的最少移動次數(shù)。

【數(shù)據(jù)范圍】

????????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]=1while q:tx,ty,step = q.popleft()if tx==n and ty==m:print(step)returnfor x_,y_ in dir:nx,ny = tx+x_,ty+y_if nx<1 or nx>n or ny<1 or ny>m:continueif mp[nx][ny]==1 or st[nx][ny]:continueq.append( [nx,ny,step+1] )st[nx][ny]=1
bfs()

---

?試題三：八數(shù)碼

【題目描述】

????????在一個?3×3 的網(wǎng)格中，1～8這?8 個數(shù)字和一個?x?恰好不重不漏地分布在這?3×3的網(wǎng)格中。

例如：

1 2 3
x 4 6
7 5 8

????????在游戲過程中，可以把?x?與其上、下、左、右四個方向之一的數(shù)字交換（如果存在）。我們的目的是通過交換，使得網(wǎng)格變?yōu)槿缦屡帕?#xff08;稱為正確排列）：

1 2 3
4 5 6
7 8 x

????????例如，示例中圖形就可以通過讓?x?先后與右、下、右三個方向的數(shù)字交換成功得到正確排列。交換過程如下

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?與上下左右方向數(shù)字交換的行動記錄為?u、d、l、r?，F(xiàn)在，給你一個初始網(wǎng)格，請你通過最少的移動次數(shù)，得到正確排列。

【輸入格式】

????????輸入占一行，將?3×3?的初始網(wǎng)格描繪出來。例如，如果初始網(wǎng)格如下所示：

1 2 3 
x 4 6 
7 5 8 

????????則輸入為：1 2 3 x 4 6 7 5 8

【輸出格式】

????????輸出占一行，包含一個整數(shù)，表示最少交換次數(shù)。

????????如果不存在解決方案，則輸出??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 nidx<1 or nidx>9:continueif (sidx==3 or sidx==6) and i==1:continueif (sidx==4 or sidx==7) and i==-1:continueteps[sidx],teps[nidx] = teps[nidx], teps[sidx]nteps = "".join(teps)if  mp[nteps]:continuemp[nteps]=1q.append( [teps,nidx,step+1] )print(res)
bfs()

---

試題四：全球變暖

【題目描述】

????????你有一張某海域?N×N像素的照片，”.”表示海洋、”#”表示陸地，如下所示：

.......
.##....
.##....
....##.
..####.
...###.
.......

????????其中”上下左右”四個方向上連在一起的一片陸地組成一座島嶼，例如上圖就有?22?座島嶼。由于全球變暖導致了海面上升，科學家預測未來幾十年，島嶼邊緣一個像素的范圍會被海水淹沒。具體來說如果一塊陸地像素與海洋相鄰(上下左右四個相鄰像素中有海洋)，它就會被淹沒。例如上圖中的海域未來會變成如下樣子：

.......
.......
.......
.......
....#..
.......
.......

????????請你計算：依照科學家的預測，照片中有多少島嶼會被完全淹沒。

【輸入格式】

????????第一行包含一個整數(shù)N。

????????以下?N 行?N 列，包含一個由字符”#”和”.”構(gòu)成的?N×N字符矩陣，代表一張海域照片，”#”表示陸地，”.”表示海洋。

????????照片保證第?1行、第?1?列、第?N 行、第?N 列的像素都是海洋。

【輸出格式】

????????一個整數(shù)表示答案。

【數(shù)據(jù)范圍】

????????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 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 = tx+a,ty+bif nx<0 or nx>=n or ny<0 or ny>=n:continueif mp[nx][ny]=='.' or st[nx][ny]:continuest[nx][ny]=1if mp[nx+1][ny]==mp[nx-1][ny]==mp[nx][ny+1]==mp[nx][ny-1]=='#':flag=1q.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 +=1bfs(i,j)
print(cnt-res)

---

試題五：八數(shù)碼2

【題目描述】

????????在一個?3×3 的網(wǎng)格中，1～8這?8 個數(shù)字和一個?x?恰好不重不漏地分布在這?3×3的網(wǎng)格中。

例如：

1 2 3
x 4 6
7 5 8

????????在游戲過程中，可以把?x?與其上、下、左、右四個方向之一的數(shù)字交換（如果存在）。我們的目的是通過交換，使得網(wǎng)格變?yōu)槿缦屡帕?#xff08;稱為正確排列）：

1 2 3
4 5 6
7 8 x

????????例如，示例中圖形就可以通過讓?x?先后與右、下、右三個方向的數(shù)字交換成功得到正確排列。交換過程如下

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?與上下左右方向數(shù)字交換的行動記錄為?u、d、l、r。現(xiàn)在，給你一個初始網(wǎng)格，請你通過最少的移動次數(shù)，得到正確排列。

【輸入格式】

????????輸入占一行，將?3×3?的初始網(wǎng)格描繪出來。例如，如果初始網(wǎng)格如下所示：

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

【解題思路】

? ? ? ? 簡答題，在前面八數(shù)碼1的基礎(chǔ)上改一下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 nidx<1 or nidx>9:continueif (sidx==3 or sidx==6) and dir[i]==1:continueif (sidx==4 or sidx==7) and dir[i]==-1:continueteps[sidx],teps[nidx] = teps[nidx], teps[sidx]nteps = "".join(teps)if  mp[nteps]:continuemp[nteps]=1q.append( [teps,nidx,step+fx[i]] )if flag:print(res)else:print('unsolvable')
bfs()