2022年4月23日第十三届省赛蓝桥杯真题答案

第五题如约而至哈，和第六题差不多（但比第六题简单）。好！上题目：

题目：

有一片海域划分为N*M个方格，其中有些海域已被污染（用0表示），有些海域没被污染（用1表示）。请问这片N*M海域中有几块是没被污染的独立海域（没被污染的独立海域是指该块海域上下左右被已污染的海域包围，且N*M以外的海域都为已被污染的海域）

例如：N=4，M=5，4*5的海域中，已被污染海域和没被污染的海域如下图：

输入描述：

第一行输入两个正整数N和M，N表示矩阵方格的行，M表示矩阵方格的列，N和M之间以一个英文逗号隔开

第二行开始输入N行，每行M个数字（数字只能为1或者0，1表示没被污染的海域，0表示已被污染的海域）      

输出描述：

输出一个整数，表示N*M的海域中有几块是没被污染的独立海域

输入样例：

4,5                                                                                                                                                     

1,1,0,0,0                                                                                                                                             

1,0,1,0,0                                                                                                                                             

1,0,0,0,0                                                                                                                                             

1,1,0,1,1

输出样例：3

这题很简单，难就难在你考虑的方向。如果你看一块海。你就上下左右看一圈，看一块海，你就上下左右看一圈。我可以告诉你的是，这样行！但是麻烦死了！因为在拐角处你的电脑会算作这是两块海，有可能一块海还会被算n多次

那么我们怎么思考呢？可以采用一种“污海”的思路：找到一块海，在它的下面一直找，左面一直找，找到一个“污”一个(即把1变成0)，这样便能找到全部的未被污染的海域还能既不重复也不遗漏了！有人说那右边的和上边的怎么办，那要怪你没考虑周全，你如果一块海在上边或右边有海，那么在遍历它上面或右边时不早把这块海遍历“污染”了吗？

好，思路就是这样，概括一下就是：一、找左边   二、找下边    三、汇合（拐角成为一块海域）  四、打印

上代码：

def find_left(j,g,s,M):  # 左边找找(M后期赋值 列的意思)
    d=0  # 纯净海域数
    while g0 and s[j-1][g]==1)) and ((g0 and s[j][g-1]==1)):  
#  既满足 下边有 或者 上边有 还满足 右边有 或者 左边有 
                y+=1  # 拐角数+1

for j in range(N):
    for g in range(M):
        l=find_left(j,g,s,M)  # 左找找
        e=find_down(j+1,g,s,N)  # 下找找
        if e !=0 or l!=0:  # 看看有没有
            z+=1  # 有 纯净海域数量就+1
print(z-y)  # 打印最终结果
 

好啦，今天的代码就是这些啦，有需要的尽管拿走，有建议的尽管提，有求必应、有问必答。欢迎三连（点赞、转发、收藏），四连那就最好啦（加一个关注）嘿嘿！