2024蓝桥杯每日一题(Flood Fill)

时间:2024-03-27 15:30:03

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