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

时间:2022-10-10 23:27:51

题目大意:

  有一个冰箱有 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代码:

  

 1 import java.util.*;
 2 
 3 public class Main{
 4 
 5     static int mark[][] = new int[8][8];
 6     static char map[][] = new char[8][8];
 7 
 8     static void flip_them(int x,int y){
 9         for(int t = 1;t < 5;t ++){ mark[t][y] ++; }
10         for(int t = 1;t < 5;t ++){ mark[x][t] ++; }
11         mark[x][y] --;
12     }
13 
14     public static void main(String[] args){
15         Scanner sc = new Scanner(System.in);
16         while(sc.hasNext()){
17             int ans[][] = new int[20][2];
18             for(int i = 1;i < 5;i ++){
19                 for(int j = 1;j < 5;j ++){ mark[i][j] = 0; }
20             }
21             for(int i = 0;i < 20;i ++){ans[i][0] = 0;ans[i][1] = 0;}
22             for(int i = 1;i <= 4;i ++){
23                 String t = sc.nextLine();
24                 for(int j = 1;j <= 4;j ++){
25                     if(t.charAt(j - 1) == '-'){ map[i][j] = '-'; }
26                     else{ map[i][j] = '+'; }
27                 }
28             }
29             for(int i = 1;i < 5;i ++){
30                 for(int j = 1;j < 5;j ++){
31                     if(map[i][j] == '+'){
32                         flip_them(i,j);
33                     }
34                 }
35             }
36             int sum = 0;
37             for(int i = 1;i < 5;i ++){
38                 for(int j = 1;j < 5;j ++){
39                     if(mark[i][j] % 2 == 1){ans[sum][0] = i;ans[sum][1] = j;sum ++;}
40                 }
41             }
42             System.out.println(sum);
43             for(int i = 0;i < sum;i ++){System.out.println(ans[i][0] + " " + ans[i][1]);}
44         }
45     }
46 }