首页 > 代码库 > poj 2965 The Pilots Brothers' refrigerator
poj 2965 The Pilots Brothers' refrigerator
题目描述：
有一个4*4的矩阵，求最少次的操作，把这16个格子都变成‘-’，每次翻转（i，j）的时候，第i行，第j列也会变为相反的状态。
解题思路：
话说条条大路通罗马，这个题目也有很多种方法，1：bfs+状态压缩，2：状态压缩+枚举，3：高斯消元。这些方法都可以，我在这里就说一下我的方法。
根据每次操作的变化可以知道，对于一个矩阵，如果只有（i，j）是‘+’状态，我们把第i行，第j列的格子都操作一次全部都会变为合法状态（‘-’的，成为合法状态），我们现在对所有的不合法状态都进行此操作，我们会发现有一些格子我们操作了两次或者是偶数次，因为每个格子只有两种状态，为了使操作有意义，我们对每个格子最多操作一次，最后我们只需要统计操作奇数次的格子并输出其对应的下标即可。
题目链接：
http://poj.org/problem?id=2965
代码：
1 #include <cstdio> 2 #include <cstring> 3 #include <cstdlib> 4 5 #define N 5 6 7 char map[N]; 8 int vis[N][N]; 9 void change (int x, int y);10 void add ();11 12 int main ()13 {14 int i, j, sum, n;15 memset (vis, 0, sizeof(vis));16 17 for (i=0; i<4; i++)18 {19 scanf ("%s", map);20 for (j=0; j<4; j++)21 if (map[j] == ‘+‘)22 change (i, j);23 }24 25 add ();26 return 0;27 }28 29 void change (int x, int y)30 {31 for (int i=0; i<4; i++)32 vis[x][i]++, vis[i][y]++;33 34 vis[x][y] --;35 }36 void add ()37 {38 int i, j, num = 0;39 40 for (i=0; i<4; i++)41 for (j=0; j<4; j++)42 if (vis[i][j] % 2)43 num ++;44 printf ("%d\n", num);45 for (i=0; i<4; i++)46 for (j=0; j<4; j++)47 if (vis[i][j] % 2)48 printf ("%d %d\n", i+1, j+1);49 }
poj 2965 The Pilots Brothers' refrigerator
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。