双语题解·广搜bfs

1、Python

#设置地图大小
s=[int(i) for i in input().split()]
n=s[0]
m=s[1]
ground=[]
#加载地图
for i in range(n):
    s=input()
    ground.append([])
    for j in s:
        ground[i].append(j)
#广搜方向元组
dir=((1,0),(0,1),(-1,0),(0,-1),(1,1),(1,-1),(-1,1),(-1,-1))
#广搜函数
a=0
def bfs(x,y):
    global a
    #广搜队列
    q=[]
    q.append((x,y))
    ground[x][y]='.'
    while(len(q)):
        #获取队首元素
        tup=q.pop(0)
        #扩展新节点
        for i in dir:
            nx=tup[0]+i[0]
            ny=tup[1]+i[1]
            #判断节点是否满足要求
            if nx>=0 and nx<n and ny>=0 and ny<m and ground[nx][ny]=='W':
                #添加并更新节点
                q.append((nx,ny))
                ground[nx][ny]='.'
    a+=1
#主函数
def main():
    #指定位置执行广搜程序
    for i in range(n):
        for j in range(m):
            if(ground[i][j]=='W'):
                bfs(i,j)
    #输出结果
    print(a)
#调用主函数
main()

2、C++

#include<iostream>
#include<queue>
using namespace std;
int n,m,dir[8][2]={1,0,0,1,-1,0,0,-1,1,1,1,-1,-1,1,-1,-1},s;
char ground[1110][1110];
struct node{
    int x,y;
};
void bfs(int x,int y){
    queue<node>q;
    q.push({x,y});
    ground[x][y]='.';
    while(!q.empty()){
        node f=q.front();
        q.pop();
        for(int i=0;i<8;i++){
            int nx=f.x+dir[i][0],ny=f.y+dir[i][1];
            if(nx>=0&&nx<n&&ny>=0&&ny<m&&ground[nx][ny]=='W'){
                q.push({nx,ny});
                ground[nx][ny]='.';
            }
        }
    }
    s++;
}
int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++)for(int j=0;j<m;j++)cin>>ground[i][j];
    for(int i=0;i<n;i++)for(int j=0;j<m;j++)if(ground[i][j]=='W')bfs(i,j);
    cout<<s;
    return 0;
}