网站制作合肥,房屋设计软件app哪个好,下载网站模板怎么使用教程,张家港设计网站文章目录 一、普通枚举1. 铺地毯(1) 解题思路(2) 代码实现 2. 回文日期(1) 解题思路思路一#xff1a;暴力枚举思路二#xff1a;枚举年份思路三#xff1a;枚举月日 (2) 代码实现 3. 扫雷(2) 解题思路(2) 代码实现 二、二进制枚举1. 子集(1) 解题思路(2) 代码实现 2. 费解的… 文章目录 一、普通枚举1. 铺地毯(1) 解题思路(2) 代码实现 2. 回文日期(1) 解题思路思路一暴力枚举思路二枚举年份思路三枚举月日 (2) 代码实现 3. 扫雷(2) 解题思路(2) 代码实现 二、二进制枚举1. 子集(1) 解题思路(2) 代码实现 2. 费解的开关(1) 解题思路(2) 代码实现 3. even parity(1) 解题思路(2) 代码实现 一、普通枚举
顾名思义就是把所有情况全部罗列出来然后找到符合题目要求的那一个因此它是一种纯暴力的算法。
一般情况下枚举策略都是会超时的。此时要先根据题目的数据范围来判断暴力枚举是否可以通过。 如果不行的话就要考虑用其他各种算法来进行优化比如⼆分双指针前缀和与差分等。
使用枚举策略时重点思考枚举的对象枚举什么枚举的顺序正序还是逆序以及枚举的方式普通枚举⼆进制枚举递归枚举。
1. 铺地毯
【题目链接】 [P1003 NOIP 2011 提高组] 铺地毯 - 洛谷 【题目描述】 为了准备一个独特的颁奖典礼组织者在会场的一片矩形区域可看做是平面直角坐标系的第一象限铺上一些矩形地毯。一共有 n n n 张地毯编号从 1 1 1 到 n n n。现在将这些地毯按照编号从小到大的顺序平行于坐标轴先后铺设后铺的地毯覆盖在前面已经铺好的地毯之上。 地毯铺设完成后组织者想知道覆盖地面某个点的最上面的那张地毯的编号。注意在矩形地毯边界和四个顶点上的点也算被地毯覆盖。 【输入格式】 输入共 n 2 n 2 n2 行。 第一行一个整数 n n n表示总共有 n n n 张地毯。 接下来的 n n n 行中第 i 1 i1 i1 行表示编号 i i i 的地毯的信息包含四个整数 a , b , g , k a ,b ,g ,k a,b,g,k每两个整数之间用一个空格隔开分别表示铺设地毯的左下角的坐标 ( a , b ) (a, b) (a,b) 以及地毯在 x x x 轴和 y y y 轴方向的长度。 第 n 2 n 2 n2 行包含两个整数 x x x 和 y y y表示所求的地面的点的坐标 ( x , y ) (x, y) (x,y)。 【输出格式】 输出共 1 1 1 行一个整数表示所求的地毯的编号若此处没有被地毯覆盖则输出 -1。 【示例一】 输入 3
1 0 2 3
0 2 3 3
2 1 3 3
2 2输出 3【示例二】 输入 3
1 0 2 3
0 2 3 3
2 1 3 3
4 5输出 -1【说明/提示】 【样例解释 1】 如下图 1 1 1 号地毯用实线表示 2 2 2 号地毯用虚线表示 3 3 3 号用双实线表示覆盖点 ( 2 , 2 ) (2,2) (2,2) 的最上面一张地毯是 3 3 3 号地毯。 【数据范围】 对于 30 % 30\% 30% 的数据有 n ≤ 2 n \le 2 n≤2。 对于 50 % 50\% 50% 的数据 0 ≤ a , b , g , k ≤ 100 0 \le a, b, g, k \le 100 0≤a,b,g,k≤100。 对于 100 % 100\% 100% 的数据有 0 ≤ n ≤ 10 4 0 \le n \le 10^4 0≤n≤104, 0 ≤ a , b , g , k ≤ 10 5 0 \le a, b, g, k \le {10}^5 0≤a,b,g,k≤105。 noip2011 提高组 day1 第 1 1 1 题。 (1) 解题思路
枚举每一个地毯判断该该点是否被这个地毯覆盖。注意枚举的时候最好逆序枚举。因为我们需要找的是最上面的地毯如果顺序枚举的话那么必须要枚举完所有情况才能找到最上面的地毯而逆序枚举的话所找到第一个覆盖的地毯一定是最上面的地毯。
在判断一个点是否被一个地毯覆盖的时候只需要用到简单的数学知识即可。假设地毯左下角点的坐标为 (a, b)由题意这张地毯的右上角点的坐标为 (a g, b k)。那么如果一个点 (x, y) 被覆盖一定有 a x a g 且 b y b k。 (2) 代码实现
#includeiostreamusing namespace std;const int N 1e4 10;
int a[N], b[N], g[N], k[N];
int n, x, y;// 寻找最上面的地毯并返回其下标没找到返回-1
int find()
{for(int i n; i 1; --i) // 逆序枚举每一个地毯{if(x a[i] x a[i] g[i] y b[i] y b[i] k[i]){return i;}}return -1;
}int main()
{cin n;for(int i 1; i n; i)cin a[i] b[i] g[i] k[i];cin x y;cout find();return 0;
}2. 回文日期
【题目链接】 [P2010 NOIP 2016 普及组] 回文日期 - 洛谷 【题目描述】 在日常生活中通过年、月、日这三个要素可以表示出一个唯一确定的日期。 牛牛习惯用 8 8 8 位数字表示一个日期其中前 4 4 4 位代表年份接下来 2 2 2 位代表月份最后 2 2 2 位代表日期。显然一个日期只有一种表示方法而两个不同的日期的表 示方法不会相同。 牛牛认为一个日期是回文的当且仅当表示这个日期的 8 8 8 位数字是回文的。现在牛牛想知道在他指定的两个日期之间包含这两个日期本身有多少个真实存在的日期是回文的。 一个 8 8 8 位数字是回文的当且仅当对于所有的 i i i 1 ≤ i ≤ 8 1 \le i \le 8 1≤i≤8从左向右数的第 i i i 个数字和第 9 − i 9-i 9−i 个数字即从右向左数的第 i i i 个数字是相同的。 例如 对于 2016 年 11 月 19 日用 8 8 8 位数字 20161119 20161119 20161119 表示它不是回文的。对于 2010 年 1 月 2 日用 8 8 8 位数字 20100102 20100102 20100102 表示它是回文的。对于 2010 年 10 月 2 日用 8 8 8 位数字 20101002 20101002 20101002 表示它不是回文的。 每一年中都有 12 12 12 个月份 其中 1 , 3 , 5 , 7 , 8 , 10 , 12 1, 3, 5, 7, 8, 10, 12 1,3,5,7,8,10,12 月每个月有 31 31 31 天 4 , 6 , 9 , 11 4, 6, 9, 11 4,6,9,11 月每个月有 30 30 30 天而对于 2 2 2 月闰年时有 29 29 29 天平年时有 28 28 28 天。 一个年份是闰年当且仅当它满足下列两种情况其中的一种 这个年份是 4 4 4 的整数倍但不是 100 100 100 的整数倍这个年份是 400 400 400 的整数倍。 例如 以下几个年份都是闰年 2000 , 2012 , 2016 2000, 2012, 2016 2000,2012,2016。以下几个年份是平年 1900 , 2011 , 2014 1900, 2011, 2014 1900,2011,2014。 【输入格式】 两行每行包括一个 8 8 8 位数字。 第一行表示牛牛指定的起始日期。 第二行表示牛牛指定的终止日期。 保证 d a t e 1 \mathit{date}_1 date1 和 d a t e 2 \mathit{date}_2 date2 都是真实存在的日期且年份部分一定为 4 4 4 位数字且首位数字不为 0 0 0。 保证 d a t e 1 \mathit{date}_1 date1 一定不晚于 d a t e 2 \mathit{date}_2 date2。 【输出格式】 一个整数表示在 d a t e 1 \mathit{date}_1 date1 和 d a t e 2 \mathit{date}_2 date2 之间有多少个日期是回文的。 【示例一】 输入 20110101
20111231输出 1【示例二】 输入 20000101
20101231输出 2【说明/提示】 【样例说明】 对于样例 1符合条件的日期是 20111102 20111102 20111102。 对于样例 2符合条件的日期是 20011002 20011002 20011002 和 20100102 20100102 20100102。 【子任务】 对于 60 % 60 \% 60% 的数据满足 d a t e 1 d a t e 2 \mathit{date}_1 \mathit{date}_2 date1date2。 (1) 解题思路 思路一暴力枚举
最容易想到的就是设置一个变量 cnt 记录回文日期的个数枚举两个日期中间的所有数字判断是否是回文日期如果是那么判断是否是一个合法的日期如果合法那么 cnt。 思路二枚举年份
在暴力枚举的过程中我们实际上枚举了很多没有用的数字。通过观察可以发现如果一个日期数字的前四位也就是年份确定了的话那么它的后四位也就随之确定了。比如 2010 2010 2010想要构成回文日期的话那么它的后四位必定是 0102 0102 0102。因此我们仅需枚举前四位年份再加判断是否合法即可。 思路三枚举月日
枚举年份的情况有可能还是太多了我们可以只枚举月日即枚举后四位那么年份也就确定了。而在这种情况下我们仅需最多枚举 365 / 366 种情况将日月组成的数字倒过来拼成年份的数字最终将组成的回文日期与题目给的日期作比较判断是否在题目给定的范围之内即可大大减少了时间复杂度。 (2) 代码实现
#includeiostreamusing namespace std;int date1, date2;
int day[] {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};int main()
{cin date1 date2;int cnt 0;for(int i 1; i 12; i){for(int j 1; j day[i]; j){int y (j % 10) * 1000 (j / 10) * 100 (i % 10) * 10 (i / 10); // 倒过来拼成年份int num y * 10000 i * 100 j; // 拼成回文日期if(date1 num num date2) cnt; // 判断是否在题目给定的范围内}}cout cnt;return 0;
}3. 扫雷
【题目链接】 [P2327 SCOI2005] 扫雷 - 洛谷 【题目描述】 相信大家都玩过扫雷的游戏。那是在一个 n × m n\times m n×m 的矩阵里面有一些雷要你根据一些信息找出雷来。万圣节到了“余”人国流行起了一种简单的扫雷游戏这个游戏规则和扫雷一样如果某个格子没有雷那么它里面的数字表示和它 8 8 8 连通的格子里面雷的数目。现在棋盘是 n × 2 n\times 2 n×2 的第一列里面某些格子是雷而第二列没有雷如下图 由于第一列的雷可能有多种方案满足第二列的数的限制你的任务即根据第二列的信息确定第一列雷有多少种摆放方案。 【输入格式】 第一行为 N N N第二行有 N N N 个数依次为第二列的格子中的数。 1 ≤ N ≤ 10000 1\le N\le10000 1≤N≤10000 【输出格式】 一个数即第一列中雷的摆放方案数。 【示例一】 输入 2
1 1输出 2(2) 解题思路
通过观察可以发现当我们确定第一列第一个位置是否有雷时那么第一列雷的排列情况也就全部确定了。所以我们仅需枚举出第一列第一个位置放或不放地雷两种情况然后检查这两种情况下的地雷分布是否合法。
具体来说我们可以用两个数组 a[N] 和 b[N] 来保存第一列地雷分布情况0 表示无地雷1 表示有地雷和第二列的数字。那么第一列的第 i 个位置是否有地雷就可以这样计算a[i] b[i - 1] - a[i - 2] - a[i - 1]如果 a[i] 小于 0 或大于 1说明这种情况不合法即不存在这种情况。
还需要注意两个细节问题 两数组的下标可以从 1 开始计数因为当第一个位置确定之后我们是从第二个位置开始枚举的如果从下标为 0 开始计数则对应 a[1]计算时的 a[i - 2] 会发生越界的情况。所以从下标为 1 开始计数可以有效避免这种情况。 如果一共有 n 个数那么循环遍历要遍历到下标 n 1 处当 a[n 1] 不为 0 的时候同样也是不合法的情况。比如当第二列是数字 1, 3 时实际上是不合法的这个时候我们可以通过计算 a[3] 的位置是否为 0 来判断。 (2) 代码实现
#includeiostreamusing namespace std;const int N 1e4 10;
int a[N], b[N];
int n;int check1()
{a[1] 0;for(int i 2; i n 1; i){a[i] b[i - 1] - a[i - 1] - a[i - 2];if(a[i] 0 || a[i] 1) return 0; // 不合法的情况}if(a[n 1] 0) return 1;else return 0; // n 1 位置不为 0 也是不合法的
}int check2()
{a[1] 1;for(int i 2; i n 1; i){a[i] b[i - 1] - a[i - 1] - a[i - 2];if(a[i] 0 || a[i] 1) return 0;}if(a[n 1] 0) return 1;else return 0;
}int main()
{cin n;for(int i 1; i n; i) cin b[i];int ans 0;ans check1(); // a[1] 不放地雷ans check2(); // a[1] 放地雷cout ans;return 0;
}二、二进制枚举
二进制枚举用一个数二进制表示中的 0/1 表示两种状态从而达到枚举各种情况。 注利用二进制枚举时会用到⼀些位运算的知识。 多说无益直接实战 1. 子集
【题目链接】 78. 子集 - 力扣LeetCode 【题目描述】 给你⼀个整数数组 nums 数组中的元素互不相同。返回该数组所有可能的⼦集幂集。 解集不能包含重复的⼦集。你可以按任意顺序返回解集。 【示例一】 输⼊ nums [1,2,3] 输出 [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]](1) 解题思路
可以发现数组 nums 中的数字都有选或不选两种情况那么我们可以用 0 和 1 分别来表示不选和选这两种状态。通过二进制的方式来枚举出所有的子集。并且含有 n 个数的集合其子集一共有 2 ^ n 个即 1 n 个。
于是当我们有了一个二进制数比如 101 时表示第 13 位要放到子集中形成 [1, 3]。那么如何用代码实现对应位的取舍呢我们可以用一个变量 i 遍历二进制的每一位如果第 i 位为 1那么表示取那么对应的 nums[i] 就存放在一个子集中。
判断第 i 位是否为 1(对应的二进制数 i) 1。
原理就是把这个二进制数的第 i 位移到最低位然后和 1 进行按位与操作如果这个位是 1那么结果就是 1否则为 0。
十进制二进制子集判断取舍用 i 遍历二进制的每一位0000[]所有位为 0都不取1001[1]i 0: 001 0 1 1 (取)2010[2]i 1: 010 1 1 1 (取)3011[1,2]i 0, 1 为真4100[3]i 2: 100 2 1 1 (取)5101[1,3]i 0, 2 为真6110[2,3]i 1, 2 为真7111[1,2,3]所有位为真都取 (2) 代码实现
class Solution
{
public:vectorvectorint subsets(vectorint nums) {vectorvectorint ret;int n nums.size();for(int st 0; st (1 n); st) // 枚举 0~(2^n - 1){vectorint tmp; // 存储子集for(int i 0; i n; i){// 如果 st 对应的二进制的第 i 位为 1那么就放进子集中if((st i) 1) tmp.push_back(nums[i]);}ret.push_back(tmp);}return ret;}
};2. 费解的开关
【题目链接】 P10449 费解的开关 - 洛谷 【题目描述】 你玩过“拉灯”游戏吗 25 25 25 盏灯排成一个 5 × 5 5 \times 5 5×5 的方形。 每一个灯都有一个开关游戏者可以改变它的状态。 每一步游戏者可以改变某一个灯的状态。 游戏者改变一个灯的状态会产生连锁反应和这个灯上下左右相邻的灯也要相应地改变其状态。 我们用数字 1 1 1 表示一盏开着的灯用数字 0 0 0 表示关着的灯。 下面这种状态 10111 01101 10111 10000 11011 在改变了最左上角的灯的状态后将变成 01111 11101 10111 10000 11011 再改变它正中间的灯后状态将变成 01111 11001 11001 10100 11011 给定一些游戏的初始状态编写程序判断游戏者是否可能在 6 6 6 步以内使所有的灯都变亮。 【输入格式】 第一行输入正整数 n n n代表数据中共有 n n n 个待解决的游戏初始状态。 以下若干行数据分为 n n n 组每组数据有 5 5 5 行每行 5 5 5 个字符。 每组数据描述了一个游戏的初始状态。 各组数据间用一个空行分隔。 【输出格式】 一共输出 n n n 行数据每行有一个小于等于 6 6 6 的整数它表示对于输入数据中对应的游戏状态最少需要几步才能使所有灯变亮。 对于某一个游戏初始状态若 6 6 6 步以内无法使所有灯变亮则输出 -1。 【示例一】 输入 3
00111
01011
10001
11010
1110011101
11101
11110
11111
1111101111
11111
11111
11111
11111输出 3
2
-1【说明/提示】 测试数据满足 0 n ≤ 500 0 n \le 500 0n≤500。 (1) 解题思路
通过思考我们可以发现按灯这样的操作具有以下三点 性质
每一盏灯最多只会按一次 这是因为一盏灯只有开或者关两个状态所以当一盏灯被按两次的时候与它不被按的情况是等价的被按三次的时候与它被按一次是等价的以此类推。 按灯的先后顺序不会影响最终的结果 第一行的按法确定了之后后续灯的按法就跟着确定了 因为当第一行按了以后假如说变成 00101那么第二行只能去按第1, 2, 4 个位置才能使第一行的三个 0 变成 1后面第三行和第四行是影响不到第一行的状态的。所以第一行确定了那么其余行也就确定了。 有了这三点性质之后我们就可以确定我们的解题思路了 枚举出第一行的按法。由于灯只有 1 和 0 两种状态因此使用二进制枚举根据第一行的按法计算出第一行和第二行被按之后的新状态。根据第一行的结果推导出第二行的按法第三、四、五行同理。按完最后一行判断所有灯是否全亮。 如何枚举出第一行所有的按法
由于每一行有五盏灯所以二进制枚举的时候只需从 00000 枚举到 11111 2 5 − 1 2^5 - 1 25−1即可。0 代表这个位置不按1 代表按。
对于一个二进制数按法如何计算出有多少个 1按了多少次
只需下面的方式即可
// 计算二进制数中 1 的个数
int calc(int x)
{ int cnt 0;while(x){cnt;x x - 1;}return cnt;
}可以在草稿纸上试一下按位与几次就会拿掉几个 1。
如何存储灯的初始状态
我们可以用二进制来存储每一行的灯的开关状态比如第一行的灯是 00110那么我们只需要在一个一维数组中的第一位存储一个 00110 这个二进制数即可。
这里还有一个小技巧就是我们可以把 1 转化成 00 转化成 1这样反过来存储问题就变成了把灯全部变成 0 要多少步这样的话当我们判断是否是全灭的时候仅需看最后一行对应存储的值是否为 0 即可。当然这样转化还有其他好处一会儿会提到。
如何根据一个按灯方式 push计算出当前行 a[i] 以及下一行 a[i 1] 被按之后的状态
对于 a[i] 行来说我们可以用位运算快速计算得到。对于一行灯的状态 a[i] 如 10111给定一种按灯方式 push 如 00100我们仅需使用 a[i] a[i] ^ push ^ (push 1) ^ (push 1) 就可以让对应位置及其左右两边的灯的状态改变因为 1、0 这两个数异或 1 就可以实现 1 变 00 变 1。
但是这里有一个小小的问题的就是 push 1 可能会让第 5 位变成 1这是一个非法的位置可能会影响后续的判断因此我们需要截断高位。这个时候只需让计算后的 a[i] 按位与上 111110 即可即 (1 5) - 1。
所以计算 a[i] 的公式为a[i] a[i] ^ push ^ (push 1) ^ (push 1) ((1 n) - 1))。
计算第 a[i 1] 行就比较简单了只需要修改 push 中对应为 1 的位置不需要管左右易得 a[i 1] a[i 1] ^ push。
如何求下一行怎么按
我们的问题已经转化成了变成全灭因此我们的 a[i 1] 的需要按的位置只能是上一行 a[i] 亮着的位置恰好就是 a[i]即 next_push a[i]。这也是将问题转化成全灭的好处之一。 (2) 代码实现
#includeiostream
#includecstringusing namespace std;const int N 10;
int n 5;
int a[N]; // 存储每一行灯的状态
int t[N]; // a数组的备份// 计算一个二进制数中有多少个 1
int calc(int x)
{int cnt 0;while(x){cnt;x (x - 1);}return cnt;
}int main()
{int T; cin T;while(T--){// 有多组测试用例时记得清空上一轮的数据memset(a, 0, sizeof(a));// 读入数据for(int i 0; i n; i){for(int j 0; j n; j){char ch; cin ch;// 正常情况下应该是: if(ch 1) a[i] | 1 j;// 现在我们反着来存if(ch 0) a[i] | 1 j;}}int ans 0x3f3f3f3f; // 记录最终需要的最小操作数// 二进制枚举出第一行每一种情况for(int st 0; st (1 n); st){memcpy(t, a, sizeof(a));int push st; // 当前情况下的按法int cnt 0; // 当前情况下所需的最小操作数// 从上到下按每一行for(int i 0; i n; i){cnt calc(push); // 计算每一行按了多少次t[i] t[i] ^ push ^ (push 1) ^ (push 1); // 计算当前行按之后的状态t[i] (1 n) - 1; // 清除影响t[i 1] ^ push; // 计算下一行按之后的状态push t[i]; // 下一行的按法}if(t[n - 1] 0) ans min(ans, cnt); // 如果能全灭更新最小操作数}if(ans 6) cout -1 endl;else cout ans endl;}return 0;
}3. even parity
【题目链接】 UVA11464 Even Parity - 洛谷 【题目描述】 给你一个 n × n n \times n n×n 的 01 01 01 矩阵每个元素非 0 0 0 即 1 1 1你的任务是把尽量少的 0 0 0 变成 1 1 1使得原矩阵便为偶数矩阵矩阵中每个元素的上、下、左、右的元素如果存在的话之和均为偶数。 【输入格式】 输入的第一行为数据组数 T T T T ≤ 30 T \le 30 T≤30。每组数据第一行为正整数 n n n 1 ≤ n ≤ 15 1 \le n \le 15 1≤n≤15接下来的 n n n 行每行包含 n n n 个非 0 0 0 即 1 1 1 的整数相邻整数间用一个空格隔开。 【输出格式】 对于每组数据输出被改变的元素的最小个数。如果无解输出 − 1 -1 −1。 【示例一】 输入 3
3
0 0 0
0 0 0
0 0 0
3
0 0 0
1 0 0
0 0 0
3
1 1 1
1 1 1
0 0 0输出 Case 1: 0
Case 2: 3
Case 3: -1(1) 解题思路
这道题与上一道题很相似我们也可以发现当我们把第一行的改变情况确定了之后那么后面的改变状态也随之确定。因此还是可以枚举第一行所有的改变情况。
如何枚举出第一行所有的按法
同上道题一样我们从 0 枚举到 (1 n) - 1。但是需要注意的是不是所有的情况都是合法的因为这道题只能从 0 变成 1因此我们还需要判断每一行的最终情况是否合法。如果都是 0 变 1则合法计数如果不合法跳出本次循环枚举下一个状态。
如何根据一个改变方式 change计算出下一行 a[i 1] 的状态
如果一个 a[i] 的某一个位置被改变后我们需要计算 a[i 1] 对应的位置也就是 a[i] 的正下方需要这个位置的上下左右数字之和为偶数也就是上下左右的 0 的个数为偶数或者 1 的个数为偶数。由异或的性质可知这个位置的上下左右的异或结果为 0求下方的数实际上就是上左右三个数的异或结果。所以有 a[i 1] a[i - 1] ^ (a[i] 1) ^ (a[i] 1)。 (2) 代码实现
#includeiostream
#includecstringusing namespace std;const int N 20;
int n;
int a[N];
int t[N];int calc(int x, int y) // t[i], change
{int sum 0;for(int j 0; j n; j){// 如果 t[i] 的第 j 位是 1 而 change 的第 j 位是 0 则不合法返回-1if(((x j) 1) 1 ((y j) 1) 0) return -1;// 如果 t[i] 的第 j 位是 0 而 change 的第 j 位是 1 则合法并统计一次次数if(((x j) 1) 0 ((y j) 1) 1) sum;}return sum;
}int solve()
{int ret 0x3f3f3f3f; // 记录最终所需的最小操作数// 枚举第一行的所有改变情况for(int st 0; st (1 n); st){memcpy(t, a, sizeof(a));int change st; // 每一行的改变情况int cnt 0; // 记录当前情况下的最小操作数bool flag true;for(int i 1; i n; i){int c calc(t[i], change); // 判断是否合法,若合法则计算操作次数if(c -1) // 如果不合法{flag false;break;}// 如果合法cnt c; // 统计改变次数t[i] change; // 当前行的最终状态change t[i - 1] ^ (t[i] 1) ^ (t[i] 1); // 下一行的状态change (1 n) - 1; // 清除影响}if(flag) ret min(ret, cnt);}if(ret 0x3f3f3f3f) return -1;else return ret;
}int main()
{int T; cin T;for(int k 1; k T; k){memset(a, 0, sizeof(a));cin n;// 用二进制来读入数据for(int i 1; i n; i){for(int j 0; j n; j){int x; cin x;if(x) a[i] | 1 j;}}printf(Case %d: %d\n, k, solve());}return 0;
}
