2019今日头条研发岗笔试---编程题《世界杯开幕》

题目描述：世界杯开幕式在球场C举行，球场C的球迷看台可以容纳MN个球迷。在球场售票完成后，现官方想统计此次开幕式一共有多少个球队球迷群体，最大的球队球迷群体有多少人。
经调研发现，球迷群体在选座时有以下特性：
1.同球队的球迷群体会选择相邻座位，不同球队的球迷群体会选择不相邻的座位。（注：相邻包括前后相邻，左右相邻，斜对角相邻）
2.给定一个MN的二维球场，0代表该位置没有坐人，1表示该位置已有球迷，希望输出球迷群体个数P，最大的球队群体人数Q。

示例：         [0,0,0,0,0,0,0,0,0,0],
              [0,0,0,1,1,0,1,0,0,0],
              [0,1,0,0,0,0,0,1,0,1],
              [1,0,0,0,0,0,0,0,1,1],
              [0,0,0,1,1,1,0,0,0,1],
              [0,0,0,0,0,0,1,0,1,1],
              [0,1,1,0,0,0,0,0,0,0],
              [0,0,0,1,0,1,0,0,0,0],
              [0,0,1,0,0,1,0,0,0,0],
              [0,1,0,0,0,0,0,0,0,0]
输出：6  8

分析：这个题就是一个求连通区域的题目。对区域进行标记，然后做统计即可。比较麻烦的是边界元素的处理。

import numpy as np
a = np.array([[0,0,0,0,0,0,0,0,0,0],
              [0,0,0,1,1,0,1,0,0,0],
              [0,1,0,0,0,0,0,1,0,1],
              [1,0,0,0,0,0,0,0,1,1],
              [0,0,0,1,1,1,0,0,0,1],
              [0,0,0,0,0,0,1,0,1,1],
              [0,1,1,0,0,0,0,0,0,0],
              [0,0,0,1,0,1,0,0,0,0],
              [0,0,1,0,0,1,0,0,0,0],
              [0,1,0,0,0,0,0,0,0,0]
              ])
b=[[0]*10]*10
b=np.array(b)
#print(a)
h=0
cut=0
for m in range(10):
    for n in range(10):
          x=y=z=w=0
          if a[m][n]==1:
             if m>=1:
                 x=b[m-1][n]
                 if n<9:
                    y=b[m-1][n+1]
             if n>=1:
                 z=b[m][n-1]
                 if m>=1:
                    w=b[m-1][n-1]
             if x|y|z|w!=0:
               minx=max(x,y,z,w)
               if x>0 & x<minx:
                   minx=x
               if y > 0 & y < minx:
                   minx = y
               if z>0 & z<minx:
                   minx=z
               if w > 0 & w < minx:
                   minx = w
               b[m][n]=minx
               if max(x,y,z,w)!=minx:
                   if x > minx:
                       b[m - 1][n]=b[m][n]
                   if y > minx:
                       b[m - 1][n+1] = b[m][n]
                   if z > minx:
                       b[m][n-1] = b[m][n]
                   if w> minx:
                       b[m - 1][n-1] = b[m][n]
               #b[m][n]=max(x,y,z,w)
             else:
               h=h+1
               b[m][n]=h
print(b)
c=[0]*(h+1)
for m in range(10):
    for n in range(10):
        if b[m][n]!=0:
            c[b[m][n]]+=1
print("一共有"+str(len(c)-c.count(0))+"支球队")
print("人数最多的球队有"+str(max(c))+"人")