题目大意:
有一个冰箱有 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 }