【枚举暴力】【UVA11464】 Even Parity
发布日期:2021-08-26 19:01:49 浏览次数:6 分类:技术文章

本文共 2452 字,大约阅读时间需要 8 分钟。

Description

  给你一个0/1矩阵,可以将矩阵中的0变成1,问最少经过多少此操作使得矩阵任意一元素四周的元素和为偶数。

Input

 第一行是一个整数T代表数据组数,每组数据包含以下内容:

  • 第一行是一个整数n,代表矩阵的行列数
  • 接下来n行每行n个用空格隔开的整数,代表矩阵元素。

Output

 对于每组数据输出一行,格式为Case X: ans

Sample Input

330 0 00 0 00 0 030 0 01 0 00 0 031 1 11 1 10 0 0

Sample Output

Case 1: 0Case 2: 3Case 3: -1

Hint

1≤n≤15,数据不超过30组。

Solution

考虑爆搜,显然超时。

考虑如果我们知道了前i行的信息,为了保证第i行是合法的,那么第i+1行放什么元素就被唯一确定了。

换句话说,只要确定了第一行的元素,通过数学归纳法易证,整个矩阵都被唯一确定了。

考虑第一行,只有2n种可能,由于n≤15,完全可以进行枚举。后面依据前面的元素进行判断,复杂度为O(n2),合并复杂度上届为O(2nn2),已经可以通过本题。

通过一些简单的剪纸,程序可以跑的飞快,40ms在lg rk1。

Code

#include
#include
#define rg register#define ci const intinline void qr(int &x) { char ch=getchar(),lst=NULL; while(ch>'9'||ch<'0') lst=ch,ch=getchar(); while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); if (lst=='-') x=-x;}char buf[20];inline void write(int x,const char aft,const bool pt) { if(x<0) {putchar('-');x=-x;} int top=0; do { buf[++top]=x%10+'0'; x/=10; } while(x); while(top) putchar(buf[top--]); if(pt) putchar(aft);}template
inline T mmax(const T &a,const T &b) {
if(a>b) return a;return b;}template
inline T mmin(const T &a,const T &b) {
if(a
inline T mabs(const T &a) {
if(a<0) return -a;return a;}template
inline void mswap(T &a,T &b) {T temp=a;a=b;b=temp;}const int maxn = 20;const int INF = 0x3f3f3f3f;int t,n,cnt,ans;int MU[maxn][maxn];int pos[maxn][maxn];void clear();void dfs(ci,ci);void check(ci);int main() { qr(t); while(t--) { clear();qr(n); for(rg int i=1;i<=n;++i) for(int j=1;j<=n;++j) qr(MU[i][j]); dfs(1,0); if(ans==INF) ans=-1; printf("Case %d: %d\n",++cnt,ans); } return 0;}void clear() { memset(MU,0,sizeof MU); memset(pos,0,sizeof pos); n=0;ans=INF;}void dfs(ci k,ci x) { if(x>=ans) return; if(k>n) {check(x);return;} if(!MU[1][k]) { pos[1][k]=0;dfs(k+1,x); pos[1][k]=1;dfs(k+1,x+1); } else { pos[1][k]=1;dfs(k+1,x); }}void check(int x) { for(rg int i=2;i<=n;++i) { rg int di=i-1;rg int ddi=di-1; for(rg int j=1;j<=n;++j) { if((pos[di][j-1]+pos[di][j+1]+pos[ddi][j])&1) pos[i][j]=1;else pos[i][j]=0; if(pos[i][j]!=MU[i][j]) { if(MU[i][j]) return; ++x; if(x>=ans) return; } } } for(rg int i=1;i<=n;++i) { if((pos[n][i-1]+pos[n][i+1]+pos[n-1][i])&1) return; } ans=x;}

Summary

在答案依附于一个初始状态,且初始状态数可以枚举时,不妨考虑枚举初始状态,凭借此计算出终态。

这样做不仅应用于搜索题,事实上也应用于一部分DP中。

转载于:https://www.cnblogs.com/yifusuyi/p/9425990.html

转载地址:https://blog.csdn.net/weixin_33894992/article/details/94274230 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:分层开发MySchool总结
下一篇:TW实习日记:第26天

发表评论

最新留言

能坚持,总会有不一样的收获!
[***.219.124.196]2025年01月31日 07时38分50秒