首页 > 2019华为校招笔试题,最大全1连通域
头像
White69
发布于 2018-10-13 22:01
+ 关注

2019华为校招笔试题,最大全1连通域

def DFS(i,j,k,a,b):
    b[i][j]=k
    if i>0:
        if a[i-1][j]==1 and b[i-1][j]==0:
            DFS(i-1,j,k,a,b)
    if i<9:
        if a[i+1][j]==1 and b[i+1][j]==0:
            DFS(i+1,j,k,a,b)
    if j>0:
        if a[i][j-1]==1 and b[i][j-1]==0:
            DFS(i,j-1,k,a,b)
    if j<9:
        if a[i][j+1]==1 and b[i][j+1]==0:
            DFS(i,j+1,k,a,b)

上述函数为实现找出一个01矩阵a中所有上下左右相邻的1的板块(即值为1的点的连通域),使用DFS搜索每个1点的四个邻域并将该点编号,编号矩阵为b,b矩阵初始值均为0

主函数为读入一个10*10的矩阵a,初始化全0矩阵b,遍历a中每个1点并对其DFS标记

aa=[[0]*10]*10
for i in range(10):
    aa[i]=map(int,raw_input().split())
bb=[[0]*10]*10
kk=0
for ii in range(10):
    for jj in range(10):
        if aa[ii][jj]==1 and bb[ii][jj]==0:
            kk+=1
            DFS(ii,jj,kk,aa,bb)

实际运行后发现,在DFS函数中

def DFS(i,j,k,a,b):
    b[i][j]=k

b[i][j]赋值语句执行之后,并不是对b[i][j]赋值,而是对b[][j]一整列赋值

编译环境为Python2.7,Pycharm

求解这种情况出现的原因是什么,如何修改

全部评论

(2) 回帖
加载中...
话题 回帖

近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

热门推荐