判断布尔矩阵奇偶性 acm题目描述一个布尔矩阵有一种奇偶性,即该矩阵所有行和所有列的和都是偶数.下面这4×4的矩阵就具有

判断布尔矩阵奇偶性 acm
题目描述一个布尔矩阵有一种奇偶性,即该矩阵所有行和所有列的和都是偶数.下面这4×4的矩阵就具有奇偶性:1 0 1 0 0 0 0 0 1 1 1 1 0 1 0 1 它所有行的和是2,0,4,2.它所有列的和是2,2,2,2.现请你编写一个程序,读入这个矩阵并检查它是否具有奇偶性.如果没有,你的程序应当再检查一下它是否可以通过修改一位(把0修改为1,把1修改为0)来使它具有奇偶性.如果不可能,这个矩阵就被认为是破坏了.输入格式输入包含多组测试数据.每组测试数据的第一行是一个整数n(1
lanlin2004 1年前 已收到1个回答 举报

油菜花-麦杆 幼苗

共回答了15个问题采纳率:86.7% 举报

判断OK没什么好说的
注意改变(i,j)位置会影响且只会影响第i行和第j列的结果,所以可以只修改一位的情况是恰有一个行和与一个列和为奇数

1年前 追问

6

lanlin2004 举报

其实我想知道的是这题有没有什么规律之类的,可以不用一个一个的检索判断

举报 油菜花-麦杆

矩阵的每个元素至少都得读一遍, 所以复杂度至少是Θ(n^2); 而即使你不做什么优化, O(n^2)也够了, 何必在这种地方纠结
可能相似的问题
Copyright © 2024 YULUCN.COM - 雨露学习互助 - 18 q. 0.950 s. - webmaster@yulucn.com