Python广度优先算法练习

1、题目一：xxxx 1.1 问题描述

一个矩形的房间铺着红色或者黑色的方砖。一个人站在红砖上不能移动，在黑砖上可以沿着上、下、左、右4个方向移动到相邻的方砖。请编写一个程序，计算从起点出发可以到达的黑色方砖的数量（包括起点在内）。 

起点是@，要求：遍历所有黑砖。

1.2 输入格式

输入第一行是两个正整数W和H； W和H分别表示x方向和y方向上的方砖数量。W和H都是正整数并且不超过20.  

接下来有H行，每行包含W个字符。每个字符表示方砖的颜色如下。 

'.'   - 黑砖 

'＃' - 红砖  

'@' - 起点  

1.3 输出格式

输出从起点出发可以到达的黑砖的数量（包括起点在内）。

1.4 样例输入

5 4
....#
.....
#@...
.#..#

1.5 样例输出

15

1.7 运行代码

from collections import deque #导入内置库
maze=[]
W,H=map(int,input().split()) #列，行
for i in range(H):
    li=list(input())
    maze.append(li)
    for j in range(len(li)):
        if maze[i][j]=='@': #寻找起点
            st=[i,j]
#print(maze)
#print(st)
#定义上下左右移动的函数
dirs=[
    lambda x,y:(x-1,y), #上
    lambda x,y:(x+1,y), #下
    lambda x,y:(x,y-1), #左
    lambda x,y:(x,y+1) #右  
    ]
count=1
def bfs(x1,y1):
    global count,W,H
    queue=deque()
    queue.append((x1,y1))
    while len(queue)>0:
        #出队
        curNode=queue.popleft()
        #进队
        for dir in dirs:
            nextNode=dir(curNode[0],curNode[1]) #创建新节点
            if 0<=nextNode[0]<=H-1 and 0<=nextNode[1]<=W-1 \
               and maze[nextNode[0]][nextNode[1]]=='.':
                maze[nextNode[0]][nextNode[1]]='#' #将‘.’标记为#表示已经搜过
                queue.append((nextNode[0],nextNode[1]))
                count+=1
    else:
        return
bfs(st[0],st[1])
print(count)

1.8 运行结果

15

2、题目二：细胞有几个 2.1 问题描述

一矩形阵列由数字0到9组成,数字1到9代表细胞,细胞的定义为沿细胞数字上下左右还是细胞数字则为同一细胞,求给定矩形阵列的细胞个数。

如: 阵列  4  10

0234500067

1034560500

2045600671

0000000089

有4个细胞。

2.2 输入格式

输入有多行，第一行表示矩阵阵列的行数m和列数n（m<=70，n<=70）；

接下来的m行n列为0-9等10个数字构成的矩阵。

2.3 输出格式

输出细胞个数。

2.4 样例输入

4  10
0234500067
1034560500
2045600671
0000000089

2.5 样例输出

4

2.6 解题思路

一开始我是没有看懂题目的，后来我导入Excel里，才大概明白意思，就是当有1～9的数连在一起的时候，就算是一个细胞了，所以只需要创建一个广义优先搜索的函数，然后遍历整个二维列表，当发现不是0的数，使用函数将所有数都变为0，然后细胞数加一即可，依次类推，找到下一个连在一起的数。

*需要注意的是：存入二维数组的数要转为字符串型，不然就会出现(0000000089变为89的情况)

2.7 运行代码

from collections import deque
maze=[]
m,n=map(int,input().split())
for i in range(m):
    #[[234500067], [1034560500], [2045600671], [89]]
    #li=list(map(int,input().split()))
    li=list(input())
    maze.append(li)
#print(maze)
#print(st)

dirs=[
    lambda x,y:(x-1,y), #上
    lambda x,y:(x+1,y), #下
    lambda x,y:(x,y-1), #左
    lambda x,y:(x,y+1) #右  
    ]
count=0
def bfs(x1,y1):
    global count,m,n
    queue=deque()
    queue.append((x1,y1))
    while len(queue)>0:
        curNode=queue.popleft()
        for dir in dirs:
            nextNode=dir(curNode[0],curNode[1])
            #将不为0的数变为0
            if 0<=nextNode[0]<=m-1 and 0<=nextNode[1]<=n-1 \
               and maze[nextNode[0]][nextNode[1]]!='0':
                maze[nextNode[0]][nextNode[1]]='0'
                queue.append((nextNode[0],nextNode[1]))    
    else:
        return
for i in range(m):
    for j in range(n):
        if maze[i][j]!='0':
            count+=1
            bfs(i,j)
        
print(count)

2.8 运行结果

4

3、题目三：面积 3.1 问题描述

编程计算由“*”号围成的下列图形的面积。面积计算方法是统计*号所围成的闭合曲线中水平线和垂直线交点的数目。如下图所示，在10*10的二维数组中，有“*”围住了15个点，因此面积为15。

0  0  0  0  0  0  0  0  0  0

0  0  0  0  *  *  *  0  0  0

0  0  0  0  *  0  0  *  0  0

0  0  0  0  0  *  0  0  *  0

0  0  *  0  0  0  *  0  *  0

0  *  0  *  0  *  0  0  *  0

0  *  0  0  *  *  0  *  *  0

0  0  *  0  0  0  0  *  0  0

0  0  0  *  *  *  *  *  0  0

0  0  0  0  0  0  0  0  0  0

3.2 样例输入

0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 1 1 0 0 0
0 0 0 0 1 0 0 1 0 0
0 0 0 0 0 1 0 0 1 0
0 0 1 0 0 0 1 0 1 0
0 1 0 1 0 1 0 0 1 0
0 1 0 0 1 1 0 1 1 0
0 0 1 0 0 0 0 1 0 0
0 0 0 1 1 1 1 1 0 0
0 0 0 0 0 0 0 0 0 0

3.3 样例输出

15

3.4 解题思路

看到这种题，首先可以将数据导入到Excel里进行分析（如下图），这样就能很好的看出这个图形的面积为15了(里面0的个数)，该怎么做这道题呢？

首先需要创建一个10*10的二维列表来存储数，我的思路就是：因为这个图形是被1包围着的，所以可以运用BFS的方法，将图形以外的所有0标记为-1，然后遍历二维数组，找到所有的0即可。

（可以创建一个队列，先进后出的原理，当从队列中出来一个点，则往后添加他的上下左右为0的点）

但是我们的起点该从哪里开始呢？一开始我是用(0,0)这个点开始广度优先搜索的，但是测试出来的结果一直报错，后来我才知道如果该图形的边界(1)是有包含(0,1)和(1,0)这两个点的，那样我们的队列找不到下一个是0的点就会返回结果

为了解决这个问题，我们可以在二维数组的基础上添加一层外围，即添加一圈0，这样从(0,0)开始找就能放置这种情况了。

最后遍历二维列表就好了

 

 

内置队列模块的使用具体可以看这篇Python算法入门day7——队列Queue_m0_48936146的博客-CSDN博客【简单介绍】1.队列是一个数据集合，仅允许在列表的一端进行插入，另一端进行删除。2.进行插入的一端称为队尾(rear)，插入动作称为进队或入队。3.进行删除队一端称为队头(front)，删除动作称为出队。4.队列队性质：先进先出【队列队实现方式——环形队列】相比列表形式，更充分的利用了空间1.环形队列：当队首队尾指针front==Maxsize-1(队列大小)，再前进一个位置就自动到0即当rear到11时，下一跳是0，需要(11+1)%12==02.队满：(rear+https://blog.csdn.net/m0_48936146/article/details/123733959?spm=1001.2014.3001.5501

3.5 运行代码

from collections import deque #Python内置队列库
n=10 #10行10列

#将外围都标记为0
maze=[[0 for _ in range(n+2)]] #创建上边0
for i in range(n): #导入数据，并左右加0
    li=[0]+list(map(int,input().split()))+[0]
    maze.append(li)
maze.append([0 for _ in range(n+2)]) #创建下边0

#上下左右移动函数
dirs=[
    lambda x,y:(x+1,y), #下
    lambda x,y:(x-1,y), #上
    lambda x,y:(x,y+1), #右
    lambda x,y:(x,y-1)  #左
    ]
#广度优先搜索
def bfs(x1,y1):
    global n #全局变量n
    q=deque() #创建队列
    q.append((x1,y1)) #先将第一个点存入队列
    while len(q)>0: #队列为空就退出
        curNode=q.popleft() #从左边删除一个数
        #寻找被删除数的上下左右的值
        for dir in dirs:
            nextNode=dir(curNode[0],curNode[1])
            #控制边界条件，加了两层，现在是12x12的二维数组了，所以是n+1
            if 0<=nextNode[0]<=n+1 and 0<=nextNode[1]<=n+1 \
               and maze[nextNode[0]][nextNode[1]]==0:
                maze[nextNode[0]][nextNode[1]]=-1 #将走过的路标记为-1
                q.append((nextNode[0],nextNode[1])) #并添加到队列中
    else: #全部找完，退出
        return

x1,y1=0,0 #起点
maze[x1][y1]=-1 #将起点标记为已经走过

count=0 #计数
bfs(x1,y1) 

#遍历所有的0
for i in range(1,len(maze)):
    for j in range(1,len(maze)):
        if maze[i][j]==0:
            count+=1
print(count)

3.6 运行结果

15