冰箱不关门之“The Pilots Brothers' refrigerator”

题目大意：

　　有一个冰箱有 4*4 共 16 个门把手，每次转动一个门把手，与它同行同列的门把手都会转动。

　　每个把手有两种状态：

　　　　　　+ 代表 关， - 代表 开

　　你要输入一个 4*4 的矩阵代表当前状态。

　　如果要开门，必须所有的把手都是开着的。

　　求最小开门步数以及输出转动门把手坐标的顺序。（x与y间隔一个空格）

　　样例输入： 　　- + - -

　　　　　　　　　 - - - -

　　　　　　　　　 - - - -

　　　　　　　 　　- + - -

　　样例输出：　　　6

　　　　　　　　　　1 1

　　　　　　　　　　1 3

　　　　　　　　　　1 4

　　　　　　　　　　4 1

　　　　　　　　　　4 3 

　　　　　　　　　　4 4

解题思路：

　　如果这道题使用枚举方法，与翻转棋类似的方法，也可以求解，不过坐标的记录是个难事。

　　此题有一个规律，也可以说是窍门。

　　首先先抛出一个问题： 如果我只想转动我当前的把手，不想改变其他的把手的状态怎么办？

　　　　经过若干次试验，我们会发现，只要你将与目标把手同行同列的把手都转一次，那么就会发现，只有自己目标把手转动了。

　　　　我们将这7次转动称之为一个周期。

　　那么我们只需要将所有的关闭把手调整一个周期，就能得到一个打开的门。

　　但是很明显，样例没有那么复杂，仅仅转动了6次，而非 2*7 = 14 次。

　　那是因为，有的把手在转动时发生了重叠，一些把手转了偶数次，一些转了奇数次。

　　显然，偶数次等于没转过，奇数次等于转了一次。

　　这样问题就完美的解决了。

AC代码：

　　

import java.util.*;

public class Main{

    static int mark[][] = new int[8][8];
    static char map[][] = new char[8][8];

    static void flip_them(int x,int y){
        for(int t = 1;t < 5;t ++){ mark[t][y] ++; }
        for(int t = 1;t < 5;t ++){ mark[x][t] ++; }
        mark[x][y] --;
    }

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            int ans[][] = new int[20][2];
            for(int i = 1;i < 5;i ++){
                for(int j = 1;j < 5;j ++){ mark[i][j] = 0; }
            }
            for(int i = 0;i < 20;i ++){ans[i][0] = 0;ans[i][1] = 0;}
            for(int i = 1;i <= 4;i ++){
                String t = sc.nextLine();
                for(int j = 1;j <= 4;j ++){
                    if(t.charAt(j - 1) == '-'){ map[i][j] = '-'; }
                    else{ map[i][j] = '+'; }
                }
            }
            for(int i = 1;i < 5;i ++){
                for(int j = 1;j < 5;j ++){
                    if(map[i][j] == '+'){
                        flip_them(i,j);
                    }
                }
            }
            int sum = 0;
            for(int i = 1;i < 5;i ++){
                for(int j = 1;j < 5;j ++){
                    if(mark[i][j] % 2 == 1){ans[sum][0] = i;ans[sum][1] = j;sum ++;}
                }
            }
            System.out.println(sum);
            for(int i = 0;i < sum;i ++){System.out.println(ans[i][0] + " " + ans[i][1]);}
        }
    }
}