题意简述

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一样用了某种神奇的枚举…如果找到了代码或者算法会更新上来~

程序样例

#include

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;
}