Description

Input

Output

Sample Input

-+--
----
----
-+--

Sample Output

6
1 1
1 3
1 4
4 1
4 3
4 4

也是一道枚举DFS。。写着到题，可以先写http://blog.csdn.net/u013487051/article/details/37310817   

两者一样的题。。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>

using namespace std;

bool door[6][6]={false};
int flag;
int step;
int x[105];
int y[105];

int all()
{
    for(int i=1; i<=4; i++)
        for(int j=1; j<=4; j++)
            if(!door[i][j])
                return 0;
    return 1;
}

void flip(int m,int n)//翻开关
{
    for(int i=1; i<=4; i++)
    {
         door[m][i]=!door[m][i];
         door[i][n]=!door[i][n];
    }
    door[m][n]=!door[m][n]; //因为被翻了偶数次，所以在翻一次

    return;
}

void dfs(int m,int n,int deep)
{
    if(deep==step)
    {
        flag=all();
        return;
    }
    if(flag||m==5)return;

    flip(m,n);       //翻开关
    if(n<4)
    {
        x[deep]=m;
        y[deep]=n;
        dfs(m,n+1,deep+1);
    }

    else
    {
        x[deep]=m;
        y[deep]=n;
        dfs(m+1,1,deep+1);
    }

    flip(m,n);      //不符合话就翻回来
    if(n<4)
        dfs(m,n+1,deep);

    else
        dfs(m+1,1,deep);
        
    return;
}

int main()
{
    char str;
    flag=0;
    for(int i=1; i<=4; i++)
        for(int j=1; j<=4; j++)
        {
            cin>>str;
            if(str=='-')
                door[i][j]=true;
        }
    for(step=0; step<=16; step++)
    {
        dfs(1, 1, 0);
        if(flag)
            break;
    }

    if(flag)
    {
        cout<<step<<endl;
        for(int i=0; i<step; i++)
            cout<<x[i]<<" "<<y[i]<<endl;
    }

    return 0;
}

/*

参考高手的高效解法：
> 证明:要使一个为‘+‘的符号变为‘-‘,必须其相应的行和列的操作数为奇数;可以证明,如果‘+‘位置对应的行和列上每一个位置都进行一次操作,则整个图只有这一‘+‘位置的符号改变,其余都不会改变.
> 设置一个4*4的整型数组,初值为零,用于记录每个点的操作数,那么在每个‘+‘上的行和列的的位置都加1,得到结果模2(因为一个点进行偶数次操作的效果和没进行操作一样,这就是取反的原理),然后计算整型数组中一的
> 个数即为操作数,一的位置为要操作的位置(其他原来操作数为偶数的因为操作并不发生效果,因此不进行操作)
*********************************
此上证其可以按以上步骤使数组中值都为‘-’
********************************
在上述证明中将所有的行和列的位置都加1后，在将其模2之前,对给定的数组状态，将所有的位置操作其所存的操作数个次数，举例，如果a[i][j]==n,则对（i,j）操作n次，当所有的操作完后，即全为‘-’的数组。
其实就是不模2的操作，作了许多的无用功。
以上的操作次序对结果无影响，如果存在一个最小的步骤，则此步骤一定在以上操作之中。（简单说下：因为以上操作已经包含了所有可改变欲改变位置的操作了）
而模2后的操作是去掉了所有无用功之后的操作，此操作同样包含最小步骤。
但模2后的操作去掉任何一个或几个步骤后，都不可能再得到全为‘-’的。（此同样可证明：因为操作次序无影响，先进行最小步骤，得到全为‘-’，如果还剩下m步，则在全为‘-’的数组状态下进行这m步操作后还得到一个全为
‘-’的数组状态，此只能是在同一个位置进行偶数次操作，与前文模2后矛盾，所以m=0），因此模2后的操作即为最小步骤的操作。
*/

代码如下：

#include <iostream>
using namespace std;

bool mark[4][4];
char s[4][4];

int main()
{
    int i,j,k;
    int ci[16],cj[16];
    int nas = 0;
    memset(mark,0,sizeof(mark));
	for(i = 0;i < 4;i++)
		cin >> s[i];
    for(i = 0;i < 4;i++)
        for(j = 0;j < 4;j++)
        {
            char c = s[i][j];
            if(c == '+')
            {
                mark[i][j] = !mark[i][j];
                for(k = 0;k < 4;k++)
                {
                    mark[i][k] = !mark[i][k];
                    mark[k][j] = !mark[k][j];
                }
            }

        }
    for(i = 0;i < 4;i++)
        for(j = 0;j < 4;j++)
            if(mark[i][j] == true)
            {
                ci[nas] = i + 1;
                cj[nas] = j + 1;
                nas ++;
            }
    printf("%d\n",nas);
    for(i = 0;i < nas;i++)
    {
        printf("%d %d\n",ci[i],cj[i]);
    }
    return 0;
}