首页 > 代码库 > uva11464 - Even Parity
uva11464 - Even Parity
应该是属于暴力枚举类型的题目
然后这个问题和开关灯的问题的解决办法很类似
然后这两个题目我都没有什么解决办法……
这种矩阵里面计数或者是寻求最少改变数字类型的题目,往往就U懵掉,只是去找规律去寻求自己所谓的正确的解法
会计算,会找规律,会递推,会多加一次然后想到再除以2……总之等等等等方法可能都已经想过,在我的认知中却没有什么思路可以解题。
也不是没有想到过逐一枚举,但是那要怎么枚举呢,要枚举到什么时候呢……想想就否定了。
而本题的正确解法就是枚举,只不过这道题和开关灯的问题一样,不需要你全部枚举,只需要你枚举一下第一行的情况,剩下的全是可以递推出来的
也就是说,对于一个有n列的矩阵来说,全部的情况只有2^n种,当n不是太大的时候,这个枚举量完全可以接受。
希望两道题过后自己可以吸收这种解决问题的方式,“枚举开头,余下递推”的思想
以下将对代码做分析:
#include <cstdio> #define M 20 int n, min, a[M][M], b[M][M]; int calcu(int x, int y)//将其上左右三面的值加起来(如果存在的话),然后返回; { int upx = x-1, upy = y,lex = x, ley = y-1,rix = x, riy = y+1,sum = 0; if(upx>=0) sum += b[upx][upy]; if(ley>=0) sum += b[lex][ley]; if(riy<n) sum += b[rix][riy]; return sum; } void solve() { for(int i = 0; i < n-1; i++) for(int j = 0; j < n; j++) b[i+1][j] = calcu(i,j)&1;//这一句的作用在于,如果是偶数,则结果是0,如果是奇数,结果是1; int cnt = 0; for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) if(a[i][j]==1&&b[i][j]==0) return;//这种情况并不满足条件,直接结束进行下一次的枚举即可,不用更新min的值 else cnt+=(a[i][j]!=b[i][j]); if(min>cnt) min = cnt; } void dfs(int cur)//利用深度优先遍历枚举第一行 { if(cur==n)//美剧完之后开始递推下面每一行的情况 { solve(); return; } b[0][cur] = 1; dfs(cur+1); b[0][cur] = 0; dfs(cur+1); } int main () { int cas, t = 0; scanf("%d",&cas); while(t++<cas) { scanf("%d",&n); for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) scanf("%d",&a[i][j]); min = 999; dfs(0);//开始枚举; printf("Case %d: ",t); if(min==999) printf("-1\n"); else printf("%d\n",min); } return 0; }
思想很重要。认认真真实现自己的思路
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。