算法-2024蓝桥杯每日一题（BFS）

备战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)

---

试题五：八数码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]=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()