首页 > 专题系列 > Java解POJ > POJ 1058 The Gourmet Club [解题报告] Java
2013
11-09

POJ 1058 The Gourmet Club [解题报告] Java

The Gourmet Club

问题描述 :

The gourmet club of ACM City has 16 members. They contracted the proprietor of the local French restaurant Chateau Java to arrange dinner parties for 5 consecutive evenings. They asked to be seated around 4 tables, 4 persons per table. They also stipulated that during the 5 evenings, every member of the club will share a table exactly once with each member of the club. Mr. I.B. Emm, the restaurateur, assigned his Maitre D’ the task of scheduling the seating for the 5 evenings. On the first evening, the Maitre D’ seated the members as they arrived and recorded their seating. Each subsequent evening, he carefully planned the seating to match the requirement that no member will be dining twice with some other member. Unfortunately, the Maitre D’ disappeared on the morning of the fourth evening. Mr. Emm was left only with his notes which included the recorded seating arrangements during the previous 3 evenings. As he was trying to schedule the seating for the remaining evenings, it dawned on him that this task may not be that easy. He is asking for your help to try and see whether the remaining two evenings can be scheduled. The following is a sample of the Maitre D’s seating arrangements during the first 3 evenings:

ABCD EFGH IJKL MNOP

AEIM BFJN CGKO DHLP

AFKP BGLM CHIN DEJO

The members of the gourmet club were identified by the letters A,B,C,…,P.

Each line represents one evening of seating with each set of four letters a single table. Thus on the first evening A dines with B, C and D etc. Write a program that will read from the input the seating arrangement of the first three evenings and will either complete the schedule or determine that the Maitre D’ screwed up.

输入:

Each data set will be 3 lines. Each line will consist of four blocks, each 4 letters long. All letters will be in upper case. Blocks will be separated by “white space”. Data sets will be separated by blank lines.

输出:

For a successful schedule, echo the input and add two lines showing the successful schedule. If it is not possible to complete the schedule, do not echo the input, but print “It is not possible to complete this schedule.” Separate output for each data set with a blank line.

样例输入:

ABCD EFGH IJKL MNOP
AEIM BFJN CGKO DHLP
AFKP BGLM CHIN DEJO

样例输出:

It is not possible to complete this schedule.

温馨提示:

If there are several solutions ,any one is ok.

解题代码:

//* @author:
import java.util.*;
public class Main{
  String result[][];
  char c[]={'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P'};

  boolean used[];

  public Main(String result[][]){
   this.result=result;
  
  }

   public static void main(String args[]){
    Scanner sc=new Scanner(System.in);

    while(true){
     String result[][]=new String[5][4];
    
    for(int i=0;i< 5;i++)
     for(int j=0;j< 4;j++){
        if(i>=3)
          result[i][j]="";
        else
          result[i][j]=sc.next();
     }
    
     Main m=new Main(result);
     
     int r=0;
     for(int x=3;x<=4;x++){
       if(!m.doIt(x)){ r+=1; break;}
     }
     if(r==0) m.show();
    }
  }
 
  private void show(){
    for(int i=0;i< 5;i++){
     for(int j=0;j< 4;j++){
        System.out.print(result[i][j]+" ");
     }
     System.out.println();
    }
    System.out.println();
   }

   
   private boolean ch(String s1,String s2){
     int x=0;
     for(int i=0;i< s1.length();i++)
        for(int j=0;j< s2.length();j++){
          if(s1.charAt(i)==s2.charAt(j)) x++;
          if(x>=2) return true;
        }
     return false;
  }

   private boolean check(StringBuffer temp){
      String s=temp.toString();
       for(int i=0;i< 5;i++)
        for(int j=0;j< 4;j++){
          if(result[i][j]!=null&&ch(result[i][j],s))
              return false;
        }
       return true;
    }
          
    public boolean doIt(int x){
      used=new boolean[16];
      int sum=0;
      int y=0;
         
    for(int i=0;i< 16;i++)
     for(int j=i+1;j< 16;j++)
       for(int k=j+1;k< 16;k++)
         for(int l=k+1;l< 16;l++){
            if(!used[i]&&!used[j]&&!used[k]&&!used[l]){
                StringBuffer s=new StringBuffer("");
                s.append(c[i]).append(c[j]).append(c[k]).append(c[l]);
                if(check(s)){
                    used[i]=true;used[j]=true;used[k]=true;used[l]=true;
                    result[x][y]=s.toString();

                     y=y+1;
                     sum=sum+1;
                }
             }
           }
        if(sum< 4){
            System.out.println("It is not possible to complete this schedule.");
            System.out.println();
            return false;
         }
        return true;
    }
      
}

  1. 可以根据二叉排序树的定义进行严格的排序树创建和后序遍历操作。如果形成的排序树相同,其树的前、中、后序遍历是相同的,但在此处不能使用中序遍历,因为,中序遍历的结果就是排序的结果。经在九度测试,运行时间90ms,比楼主的要快。

  2. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。

  3. 第二种想法,我想来好久,为啥需要一个newhead,发现是把最后一个节点一直返回到嘴上面这层函数。厉害,这道题之前没样子想过。