解决leetcode第3548题.等和矩阵分割II

3548.等和矩阵分割II

难度：困难

问题描述：

给你一个由正整数组成的mxn矩阵grid。你的任务是判断是否可以通过一条水平或一条垂直分割线将矩阵分割成两部分，使得：

分割后形成的每个部分都是非空的。

两个部分中所有元素的和相等，或者总共最多移除一个单元格（从其中一个部分中）的情况下可以使它们相等。

如果移除某个单元格，剩余部分必须保持连通。

如果存在这样的分割，返回true；否则，返回false。

注意：如果一个部分中的每个单元格都可以通过向上、向下、向左或向右移动到达同一部分中的其他单元格，则认为这一部分是连通的。

示例1：

输入：grid=[[1,4],[2,3]]

输出：true

解释：

在第0行和第1行之间进行水平分割，结果两部分的元素和为1+4=5和2+3=5，相等。因此答案是true。

示例2：

输入：grid=[[1,2],[3,4]]

输出：true

解释：

在第0列和第1列之间进行垂直分割，结果两部分的元素和为1+3=4和2+4=6。

通过从右侧部分移除2（6-2=4），两部分的元素和相等，并且两部分保持连通。因此答案是true。

示例3：

输入：grid=[[1,2,4],[2,3,5]]

输出：false

解释：

在第0行和第1行之间进行水平分割，结果两部分的元素和为1+2+4=7和2+3+5=10。

通过从底部部分移除3（10-3=7），两部分的元素和相等，但底部部分不再连通（分裂为[2]和[5]）。因此答案是false。

示例4：

输入：grid=[[4,1,8],[3,2,6]]

输出：false

解释：

不存在有效的分割，因此答案是false。

提示：

1<=m==grid.length<=105

1<=n==grid[i].length<=105

2<=m*n<=105

1<=grid[i][j]<=105

问题分析：

这个问题的处理，其实就是把一个给定的矩阵按行和列进行拆分，得到拆分出来的两个子矩阵，再把它们的元素和求出来，先比较和值是否相等，如果相等返回True，如果不相等，再找出和值大的那个子矩阵，对它按顺序进行去掉一个元素之后求和的处理，得到一个和值的列表，然后比较较小的那个和值与列表中的哪个值相等，如果有相等的情况，再检查去掉那个元素之后，矩阵是否连通，如果检查是连通的，则返回True，否则继续比较，继续分割子矩阵。如果按行和列进行分割并进行比较都没有相等或相等并连通的情况，最后返回False。

为此设计以下函数实现：

程序如下：

#判断在一个网格中，除了点（i，j）之外的点是否连通，如果是连通，返回True，否则返回False
def is_connected(a,i,j):
n=len(a)
m=len(a[0])
# print('n,m=',n,m)
if n==1 and 0<j<m-1:
return False
elif m==1 and 0<i<n-1:
return False
else:
return True

#计算一个矩阵元素之和，并返回
def get_sum_array(s):
my_sum=0
for i in s:
my_sum=my_sum+sum(i)
return my_sum

#计算一个矩阵元素之和，然后去掉一个元素之后，返回其余元素可能的和的列表
def get_sum_array_lost_one(a):
s=get_sum_array(a)
n=len(a)
m=len(a[0])
b=[]
for i in range(n):
for j in range(m):
b.append([s-a[i][j],i,j])
return b

#按行分割矩阵，i是行数
def split_array_row(s,i):
return s[:i],s[i:]

#按列分割矩阵，i是列数
def split_array_col(s,i):
left=[x[:i] for x in s]
right=[x[i:] for x in s]
return left,right

#对于一个mxn矩阵，判断是否存在一条水平或竖直线，能够将矩阵分割成和相等的两部分
def split_array_equal_sum(s):
m=len(s)
n=len(s[0])
for i in range(1,m):
up,down=split_array_row(s,i)
u = get_sum_array(up)
d = get_sum_array(down)
if u==d:
return True
else:
up, down = (up, down) if u > d else (down, up)
t=get_sum_array_lost_one(up)
down=get_sum_array(down)
for i in t:
if down==i[0] and is_connected(up,i[1],i[2]):
return True
else:
continue
for j in range(1,n):
left,right=split_array_col(s,j)
l = get_sum_array(left)
r = get_sum_array(right)
if l==r:
return True
else:
left, right = (left, right) if l > r else (right, left)
t=get_sum_array_lost_one(left)
right=get_sum_array(right)
for i in t:
if right==i[0] and is_connected(left,i[1],i[2]):
return True
else:
continue
else:
return False

#主程序
grid=eval(input('pls input grid='))
print(split_array_equal_sum(grid))

运行实例一

pls input grid=[[1,2,3]]

True

运行实例二

pls input grid=[[5],[2],[3]]

True

运行实例三

pls input grid=[[1,2,3,4]]

True

运行实例四

pls input grid=[[2,4],[1,5]]

True

运行实例五

pls input grid=[[2,3,4],[4,5,6],[7,8,10]]

False

运行实例六

pls input grid=[[2,3,4],[4,5,6],[7,8,6]]

True

对问题进行切割，准确把握每部分功能，细心实现并组合，问题解决犹如冰雪之消融，心境如天空之朗朗。