首页 > 专题系列 > Java解POJ > POJ 2965 The Pilots Brothers’ refrigerator [解题报告] Java
2013
11-12

POJ 2965 The Pilots Brothers’ refrigerator [解题报告] Java

The Pilots Brothers’ refrigerator

问题描述 :

The game “The Pilots Brothers: following the stripy elephant” has a quest where a player needs to open a refrigerator.

There are 16 handles on the refrigerator door. Every handle can be in one of two states: open or closed. The refrigerator is open only when all handles are open. The handles are represented as a matrix 4х4. You can change the state of a handle in any location [i, j] (1 ≤ i, j ≤ 4). However, this also changes states of all handles in row i and all handles in column j.

The task is to determine the minimum number of handle switching necessary to open the refrigerator.

输入:

The input contains four lines. Each of the four lines contains four characters describing the initial state of appropriate handles. A symbol “+” means that the handle is in closed state, whereas the symbol “−” means “open”. At least one of the handles is initially closed.

输出:

The first line of the input contains N – the minimum number of switching. The rest N lines describe switching sequence. Each of the lines contains a row number and a column number of the matrix separated by one or more spaces. If there are several solutions, you may give any one of them.

样例输入:

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

样例输出:

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

解题代码:

/* @author: */
import java.util.Scanner;
public class Main{
 static int gra[][]=new int[5][5];
 static char ch[]=new char[5];
 public static void main(String args[])
{
  Scanner sc=new Scanner(System.in);
   int i,j,k,f;
   for(i=1;i<=4;i++)
   { 
     ch=sc.next().toCharArray();
     
      for(j=0;j< 4;j++)
    if(ch[j]=='+'){
      for(f=1;f<=4;f++){
        gra[i][f]++;
        if(f!=i)
         gra[f][j+1]++;
      }
    }
   }
   int sum=0;
   for(i=1;i<=4;i++)
    for(j=1;j<=4;j++)
     if(gra[i][j]%2!=0)
     {
      sum++;
     }
     System.out.printf("%d\n",sum);
   for(i=1;i<=4;i++)
    for(j=1;j<=4;j++)
     if(gra[i][j]%2!=0)
     {
      System.out.printf("%d %d\n",i,j);
     }
    }
}

  1. 这道题这里的解法最坏情况似乎应该是指数的。回溯的时候
    O(n) = O(n-1) + O(n-2) + ….
    O(n-1) = O(n-2) + O(n-3)+ …
    O(n) – O(n-1) = O(n-1)
    O(n) = 2O(n-1)

  2. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。