消消乐问题：
用一个感染函数，一个标志矩阵（初始值为1），把与初始点相同且连成一片的位置，对应在标志矩阵的位置改为0，然后与初始矩阵进行对应位置相乘的操作，则初始矩阵被消除的位置变为0，其他位置数字保持不变，然后执行下沉操作，对下沉完成的矩阵继续执行开始的消除操作
开始写的版本是贪心的，就是每次消除最大数量的点，但后来感觉不合适，不是最优解。后来改成每次从上到下，从左到右顺序‘感染’，只要凑够三个就删除
从上到下，从左到右顺序消除：
import numpy as np
class returndata():#每个点给上一个点返回的信息（与本点相邻且相同的点有多少个？）
subnum = 0
def __init__(self,subnum):
self.subnum = subnum
#感染函数（给定flaglist矩阵，把能连城一片的点的位置，对应在flaglist中表为0）
def infect(i, j, number, checkerboard, flagList):
if i<0 or i >= len(checkerboard) or j<0 or j>= len(checkerboard[0]) or checkerboard[i][j] != number or \
flagList[i][j]==0 or number == 0:
return returndata(0)
flagList[i][j] = 0
sumsubnum = returndata(1)
#从上下左右四个方向继续“感染”
a = infect(i + 1, j, checkerboard[i][j], checkerboard, flagList)
b = infect(i - 1, j, number, checkerboard, flagList)
c = infect(i, j + 1, checkerboard[i][j], checkerboard, flagList)
d = infect(i, j - 1, number, checkerboard, flagList)
sumsubnum.subnum += a.subnum+b.subnum+c.subnum+d.subnum
return sumsubnum#返回值为 从此点出发，最多能删除的点的个数
#下沉函数，把不是0的数都下沉下去
def down(matrix):
for i in range(len(matrix)-1,0,-1):
for j in range(len(matrix[0])):
if matrix[i][j]==0:
for h in range(i-1,-1,-1):
if matrix[h][j]!=0:
matrix[i][j] = matrix[h][j]
matrix[h][j] = 0
return matrix
checkerboard = np.array([[3, 1, 2, 1, 1, ], \
[1, 1, 1, 1, 3], \
[1, 1, 1, 1, 1], \
[1, 1, 1, 1, 1], \
[3, 1, 2, 2, 2]])
row = checkerboard.shape[0] # 获取行数
col = checkerboard.shape[1] # 获取列数
flagList = [[1] * col for i in range(row)] # 创建标志矩阵，初始值为1，能删除的位置变为0
flagList = np.array(flagList)
#print(checkerboard)
for i in range(row):
for j in range(col):
flagList = [[1] * col for k in range(row)]#消除矩阵
flagList = np.array(flagList)
result = infect(i, j, checkerboard[i][j], checkerboard, flagList)
if result.subnum>=3:#如果相同点连通个数大于等于3，则进行消除操作
checkerboard = checkerboard*flagList
checkerboard = down(checkerboard)
print(checkerboard)
count = 0#最后剩下的不能删除的点的个数
for lst in checkerboard:
for x in lst:
if x!=0:
count+=1
print(count)
贪心版本：
import numpy as np
class returndata():#返回的信息（与本点相邻的点有多少个？）
subnum = 0
def __init__(self,subnum):
self.subnum = subnum
def infect(i, j, number, checkerboard, flagList):#感染函数
if i<0 or i >= len(checkerboard) or j<0 or j>= len(checkerboard[0]) or checkerboard[i][j] != number or \
flagList[i][j]==0 or number == 0:
return returndata(0)
flagList[i][j] = 0
sumsubnum = returndata(1)
a = infect(i + 1, j, checkerboard[i][j], checkerboard, flagList)
b = infect(i - 1, j, number, checkerboard, flagList)
c = infect(i, j + 1, checkerboard[i][j], checkerboard, flagList)
d = infect(i, j - 1, number, checkerboard, flagList)
sumsubnum.subnum += a.subnum+b.subnum+c.subnum+d.subnum
return sumsubnum
def down(matrix):#把不是0的都沉下去
for i in range(len(matrix)-1,0,-1):
for j in range(len(matrix[0])):
if matrix[i][j]==0:
for h in range(i-1,-1,-1):
if matrix[h][j]!=0:
matrix[i][j] = matrix[h][j]
matrix[h][j] = 0
return matrix
checkerboard = np.array([[3, 1, 2, 1, 1, ], \
[1, 1, 1, 1, 3], \
[1, 1, 1, 1, 1], \
[1, 1, 1, 1, 1], \
[3, 1, 2, 2, 2]])
row = checkerboard.shape[0] # 获取行数
col = checkerboard.shape[1] # 获取列数
flagList = [[1] * col for i in range(row)]
flagList = np.array(flagList)
print(checkerboard)
dic = {}#key:可删除点的个数 value：对应个数的标志矩阵（0 1矩阵）
while True:
dic.clear()
for i in range(row):
for j in range(col):
flagList = [[1] * col for k in range(row)]#消除矩阵
flagList = np.array(flagList)
result = infect(i, j, checkerboard[i][j], checkerboard, flagList)
if result.subnum>=3:
dic[result.subnum] = flagList
if dic=={}:#结束条件（不能再消除的时候结束）
break
#if max(dic.keys())<3:
# break
maxdeletematrix = dic.get(max(dic.keys()))
checkerboard = checkerboard*maxdeletematrix
checkerboard = down(checkerboard)
print(checkerboard)
count = 0#最后剩下的不能删除的点的个数
for lst in checkerboard:
for x in lst:
if x!=0:
count+=1
print(count) 