Skip to content

Latest commit

 

History

History
 
 

2128.Remove-All-Ones-With-Row-and-Column-Flips

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 

2128.Remove-All-Ones-With-Row-and-Column-Flips

假设有一系列的操作能够实现全部翻转为0,那么这些操作的顺序任意打乱,应该不影响最终效果。所以我们不妨先只做列翻转,再做行翻转。

可以想象,我想通过某些行的翻转最终实现全部为0,只可能是一种情况:这些行的元素之前已经通过若干次列翻转全部变成了1。考虑到列翻转的操作会影响到多行,这就意味着这些行的列元素必然相等。

同理,如果某些行不需要通过行翻转就能实现全部为0,只有一种情况:这些行的元素之前已经通过若干次列翻转全部变成了0。考虑到列翻转的操作会影响到多行,这就意味着这些行的列元素必然相等。

综上,原矩阵中,所有行的pattern只可能是有两种,并且这两种pattern恰好都是互斥的(即001101和110010的关系)。这样通过若干次列翻转后,就能得到若干个全部是1的行,以及若干个全部是0的行。