POJ-2965 解题报告

题意简述

4*4矩阵,填充+或-,改变某格符号将同时改变当前行和列所有的格的符号。

求最少经过多少次转换能使所有符号变为-,并输出任一种可行方案。

算法分析

本题与POJ-1753基本没有区别。仅仅换了壳,增加了输出一种可行方案。

【POJ-1753解题报告 传送门】

在POJ-1753的基础上,DFS同时用一个16个一维01数组记录当前的转换方案。与当前最优解比较时,如果更优则替换已记录的最优方案。

Problem Status: AC。时间875ms,内存388k

——————————————————————分割线——————————————————————

优化:

1、与POJ-1753一样可以使用一个int型代替一维01数组,用位运算实现转换。(还没试,改天再说…)

2、在评测记录里看到一个内存16K,时间0ms的记录…估计和POJ-1753一样用了某种神奇的枚举…如果找到了代码或者算法会更新上来~

程序样例

[c]#include<stdio.h>

int finish(int s[])
{
int i;
for(i=0;i<16;i++)
if (s[i]==0) return 0;
return 1;
}

void change(int s[],int pos)
{
int i;
if (s[pos]==1) s[pos]=0; else s[pos]=1;
for(i=0;i<16;i++)
if (i!=pos)
{
if (i%4==pos%4)
if (s[i]==1) s[i]=0; else s[i]=1;
if (i/4==pos/4)
if (s[i]==1) s[i]=0; else s[i]=1;
}
}

void try(int s[],int at[],int a[],int pos,int step,int *ans)
{
int i;
if (finish(s))
{
if (step<*ans)
{
*ans=step;
for(i=0;i<16;i++) a[i]=at[i];
}
return;
}
if (pos>15) return;
change(s,pos); at[pos]=1;
try(s,at,a,pos+1,step+1,ans);
change(s,pos); at[pos]=0;
try(s,at,a,pos+1,step,ans);
}
int main()
{
int s[16];
int i,j,ans=17,a[16]={0},at[16]={0};
char t[5];
for(i=0;i<4;i++)
{
scanf("%s",t);
for(j=0;j<4;j++)
if (t[j]==’-‘) s[i*4+j]=1;
else s[i*4+j]=0;
}
try(s,at,a,0,0,&ans);
printf("%dn",ans);
for(i=0;i<16;i++)
if(a[i]==1) printf("%d %dn",i/4+1,i%4+1);
return 0;
}
[/c]

One thought on “POJ-2965 解题报告

Leave a Reply

Your email address will not be published. Required fields are marked *