备战2024年蓝桥杯 -- 每日一题
Python大学A组
试题一：扫雷
试题二：动态网络
试题三：走迷宫
试题四：画图
试题一：扫雷
【题目描述】
扫雷是一种计算机游戏，在 2020 世纪 8080 年代开始流行，并且仍然包含在某些版本的 Microsoft Windows 操作系统中。在这个问题中，你正在一个矩形网格上玩扫雷游戏。最初网格内的所有单元格都呈未打开状态。其中 M 个不同的单元格中隐藏着 M 个地雷。其他单元格内不包含地雷。你可以单击任何单元格将其打开。如果你点击到的单元格中包含一个地雷，那么游戏就会判定失败。如果你点击到的单元格内不含地雷，则单元格内将显示一个 00 到 88 之间的数字（包括 00 和 88），这对应于该单元格的所有相邻单元格中包含地雷的单元格的数量。如果两个单元格共享一个角或边，则它们是相邻单元格。另外，如果某个单元格被打开时显示数字 00，那么它的所有相邻单元格也会以递归方式自动打开。当所有不含地雷的单元格都被打开时，游戏就会判定胜利。例如，网格的初始状态可能如下所示（* 表示地雷，而 c 表示第一个点击的单元格）：
*..*...**.
....*.....
..c..*....
........*.
..........被点击的单元格旁边没有地雷，因此当它被打开时显示数字 00，并且它的 88 个相邻单元也被自动打开，此过程不断继续，最终状态如下：
*..*...**.
1112*.....
00012*....
00001111*.
00000001.. 此时，仍有不包含地雷的单元格（用 . 字符表示）未被打开，因此玩家必须继续点击未打开的单元格，使游戏继续进行。你想尽快赢得游戏胜利并希望找到赢得游戏的最低点击次数。给定网格的尺寸（N×N），输出能够获胜的最小点击次数。
【输入格式】
第一行包含整数 T，表示共有 T 组测试数据。
每组数据第一行包含整数 N，表示游戏网格的尺寸大小。
接下来 N行，每行包含一个长度为 N的字符串，字符串由 .（无雷）和 *（有雷）构成，表示游戏网格的初始状态。
【输出格式】
每组数据输出一个结果，每个结果占一行。
结果表示为 Case #x: y，其中 x是组别编号（从 11 开始），y 是获胜所需的最小点击次数。
【输入样例】
2
3
..*
..*
**.
5
..*..
..*..
.*..*
.*...
.*...【输出样例】
Case #1: 2
Case #2: 8【解题思路】
首先可以先遍历求解出每一个‘.’的数字值，然后两层循环遍历找到值为0的点，在这个点进行BFS扩散一下，遍历完成后找到为数字的点，但是没有被扩散到。扩散次数加上为数字的点且未被扩散的数量就是答案。
【Python程序代码】
from collections import *
T = int(input())
dir = [(0,1),(0,-1),(1,0),(1,1),(1,-1),(-1,0),(-1,1),(-1,-1)]
def bfs(x,y):
q = deque()
q.append((x,y))
vis[x][y]=1
while q:
tx,ty = q.popleft()
for x_,y_ in dir:
nx,ny = tx+x_,ty+y_
if nx<0 or nx>=n or ny<0 or ny>=n:continue
if vis[nx][ny]:continue
if st[nx][ny]==0:
q.append((nx,ny))
vis[nx][ny]=1
for _ in range(T):
n = int(input())
st = [[0]*(n+5) for _ in range(n+5)]
a = []
for i in range(n):
a.append(list(input()))
for i in range(n):
for j in range(n):
for tx,ty in [(0,1),(0,-1),(1,0),(1,1),(1,-1),(-1,0),(-1,1),(-1,-1)]:
nx,ny = i+tx,j+ty
if a[i][j]=='*':
st[i][j]='*'
continue
if nx<0 or nx>=n or ny<0 or ny>=n:continue
st[i][j] += a[nx][ny]=='*'
vis = [[0]*(n+5) for _ in range(n+5)]
res = 0
for i in range(n):
for j in range(n):
if st[i][j]==0 and vis[i][j]==0:
bfs(i,j)
res += 1
for i in range(n):
for j in range(n):
if st[i][j] and vis[i][j]==0 and a[i][j]=='.':
res += 1
print("Case #%d: %d"%(_+1,res))
试题二：动态网络
【题目描述】
我们有一个 R 行 C 列的矩形网格，其中每个方格内的数字都是 0 或 1。我们将在网格上执行 N 个操作，每个操作都是以下之一：
- 操作 M：将网格的一个单元格中的数字更改为 0 或 1。
- 操作 Q：确定 1 的不同连通区域的数量。 1的连通区域是指矩阵内全部为 1 的连通的单元格的子集，在子集区域内通过沿着共享边缘在单元格之间行进，可以从该区域中的任何单元格到达该区域中的任何其他单元格。
【输入格式】
第一行包含整数 T，表示共有 T 组测试数据。
每组数据第一行包含两个整数 R和 C，表示矩形网格的行数和列数。
接下来 R 行，每行包含一个长度为 C 的由 11 和 00 构成的字符串，表示矩阵网格的初始状态。
接下来一行，包含整数 N，表示操作数量。
接下来 N 行，每行包含一个操作指令，操作指令共两种，如下所示：
-
M x y z，表示 M 指令，具体含义为将第 x 行第 y 列的方格内的值变为 z。 -
Q，表示 Q 指令，表示进行一次询问。
【输出格式】
对于每组测试数据，第一行输出 Case #x:，其中 x为组别编号（从 11 开始）。
接下来 Q 行，每行输出一个询问的结果。
【数据范围】
1≤T≤10,
1≤R,C≤100,
0≤x<R,
0≤y<C,
0≤z≤1，
1≤N≤1000
【输入样例】
1
4 4
0101
0010
0100
1111
7
Q
M 0 2 1
Q
M 2 2 0
Q
M 2 1 0
Q【输出样例】
Case #1:
4
2
2
2【解题思路】
BFS求联通块。简答题。
【Python程序代码】
from collections import *
T = int(input())
def bfs(x,y):
q = deque()
q.append([x,y])
st[x][y]=1
while q:
tx,ty = q.popleft()
for x_,y_ in [(1,0),(-1,0),(0,1),(0,-1)]:
nx,ny = tx+x_,ty+y_
if nx<0 or nx>=r or ny<0 or ny>=c:continue
if a[nx][ny]=='0' or st[nx][ny]:continue
st[nx][ny]=1
q.append([nx,ny])
for _ in range(T):
r,c = map(int,input().split())
a,res = [],[]
for i in range(r):
a.append(list(input()))
n = int(input())
for _i in range(n):
tep = input().split()
if tep[0]=='M':
a[ int(tep[1]) ][ int(tep[2])] = tep[3]
else:
ct = 0
st = [[0]*(c+1) for i in range(r+1)]
for i in range(r):
for j in range(c):
if a[i][j] == '1' and st[i][j]==0:
bfs(i,j)
ct += 1
res.append(ct)
print("Case #%d:"%(_+1))
for i in range(len(res)):
print(res[i])
试题三： 走迷宫
【题目描述】
给定一个 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【解题思路】
模板题
【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()试题四： 画图
【题目描述】
用 ASCII 字符来画图是一件有趣的事情，并形成了一门被称为 ASCII Art 的艺术。例如，下图是用 ASCII 字符画出来的 CSPRO 字样。
..____.____..____..____...___..
./.___/.___||.._.\|.._.\./._.\.
|.|...\___.\|.|_).|.|_).|.|.|.|
|.|___.___).|..__/|.._.<|.|_|.|
.\____|____/|_|...|_|.\_\\___/.本题要求编程实现一个用 ASCII 字符来画图的程序，支持以下两种操作：
- 画线：给出两个端点的坐标，画一条连接这两个端点的线段。简便起见题目保证要画的每条线段都是水平或者竖直的。水平线段用字符
-来画，竖直线段用字符|来画。如果一条水平线段和一条竖直线段在某个位置相交，则相交位置用字符+代替。 - 填充：给出填充的起始位置坐标和需要填充的字符，从起始位置开始，用该字符填充相邻位置，直到遇到画布边缘或已经画好的线段。注意这里的相邻位置只需要考虑上下左右 4 个方向，如下图所示，字符
@只和 4 个字符*相邻。
.*.
*@*
.*.【输入格式】
第 1行有三个整数 m,n 和 q。m 和 n 分别表示画布的宽度和高度，以字符为单位。q 表示画图操作的个数。
第 2 行至第 q+1 行，每行是以下两种形式之一：
-
0 x1 y1 x2 y2：表示画线段的操作，(x1,y1)和 (x2,y2)分别是线段的两端，满足要么 x1=x2 且 y1≠y2，要么 y1=y2且 x1≠x2。 -
1 x y c：表示填充操作，(x,y)是起始位置，保证不会落在任何已有的线段上；c 为填充字符，是大小写字母。
画布的左下角是坐标为 (0,0)的位置，向右为 x坐标增大的方向，向上为 y坐标增大的方向。这 q个操作按照数据给出的顺序依次执行。画布最初时所有位置都是字符 .（小数点）。
【输出格式】
输出有 n 行，每行 m 个字符，表示依次执行这 q个操作后得到的画图结果。
【输入样例】
4 2 3
1 0 0 B
0 1 0 2 0
1 0 0 A【输出样例】
AAAA
A--A【解题思路】
关键点在于输出的时候行上下对调一下，还有就是输入数据看清楚哪个对应哪个就ok，然后用BFS模拟一下就ok
【Python程序代码】
from collections import *
m,n,q = map(int,input().split())
st = [['.']*(m+5) for _ in range(n+5)]
pd = ['-','|']
def bfs(x,y,c):
q = deque()
q.append([x,y])
st[x][y]=1
while q:
tx,ty = q.popleft()
for x_,y_ in [(1,0),(-1,0),(0,1),(0,-1)]:
nx,ny = tx+x_ ,ty + y_
if nx<0 or nx>=n or ny<0 or ny>=m:continue
if vis[nx][ny] or ( st[nx][ny] in ['-','|','+'] ):continue
q.append([nx,ny])
vis[nx][ny]=1
st[nx][ny]=c
for _ in range(q):
t = input().split()
if t[0]=='0':
if t[1]==t[3]:
for i in range(min(int(t[2]),int(t[4])),max(int(t[2]),int(t[4]))+1):
if st[i][int(t[1])]=='-' or st[i][int(t[1])]=='+':
st[i][int(t[1])]='+'
else:st[i][int(t[1])] = '|'
else:
for i in range(min(int(t[1]),int(t[3])),max(int(t[1]),int(t[3]))+1):
if st[int(t[2])][i] == '|' or st[int(t[2])][i] == '+':
st[int(t[2])][i]='+'
else:st[int(t[2])][i] = '-'
else:
vis = [[0]*(m+5) for _ in range(n+5)]
bfs( int(t[2]) , int(t[1]) ,t[3] )
for i in range(n):
for j in range(m):
print(st[n-1-i][j],end='')
print()