首页 > 专题系列 > Java解POJ > POJ 1219 L-I-N-G-O: LINGO [解题报告] Java
2013
11-09

POJ 1219 L-I-N-G-O: LINGO [解题报告] Java

L-I-N-G-O: LINGO

问题描述 :

A new TV game show requires contestants to deduce a five letter word based on hints obtained by guessing other five letter words. The way the game is played is as follows: a secret five letter word is selected by the production staff of the game show. The object of the game is for the contestant to guess the secret word. The first letter of the secret word is revealed. The contestant will then guess a five letter word that may match the secret word. A computer then provides feedback to the contestant on the accuracy of the guess. Feedback consists of a report indicating if any letters in the guessed word are correct and in the same position in the secret word, if any letters in the guessed word are correct but not in the correct position in the secret word, and any letters in the guessed word that do not appear in the secret word.

As an example, the production staff chooses the secret word: “HELLO”. The contestant is told the first letter of the word is “H”. The contestant then guesses what the word could be, knowing it begins with the letter “H”. Let’s say the contestant guesses the word: “HOLES”. The game show computer would report that the “H” and “L” are in the secret word and in the correct position. In addition, the “O” and “E” are in the secret word, but in the incorrect position, and the “S” is not in the secret word. This is conveyed to the contestant by a single line report:

HoLe.

The upper case letters (“H” and “L”) indicate correct letter and position. The lower case letters (“o” and “e”) indicate correct letter, wrong position. The period (“.”) indicates a wrong letter (not in the secret word).

You will write a program that evaluates the contestant guesses, and prints out the single line report for each guess.If the contestant guesses the secret word exactly, then the five capital letters of the secret word will be displayed in the report.

输入:

The input data file consists of datasets for one or more games. A blank line marks the beginning of the next dataset (game). The line after the blank line contains the secret word. The remaining lines in the dataset represent the contestant’s guesses; there may be too few or too many guesses than are necessary to guess the secret word. The secret word will contain exactly five upper case letters. The contestant抯 guesses, however, have to be checked for validity: valid guesses consist of exactly five upper case letters. Input is terminated by a dataset with the secret word: “LINGO” (that is, game play is stopped at that point, the program terminates, and no further guessing occurs).

输出:

Each game’s output should be preceded by a single blank line (except for the terminating case). The first single line status report should be printed, which consists of the first letter of the secret word, followed by four periods. For each guess, print the single line status report for that guess. For an invalid guess, repeat the previous single line status report. If the guess exactly matches the secret word, that game ends and you should move on to the next one.The contestant may guess a maximum of six times; after the sixth guess, if the contestant did not guess the secret word, or you run out of guesses (the contestant gives up) print out the secret word in lower case letters and move on to the next game.

样例输入:


HELLO
HOLES
HAPPY
HELMS
HELLO
HELPS

PARTY
PARKS
PARES
PARIS
PONDER
PATTY
PUNTS
PARTY

HELIX
HeLIX
HELIX

LINGO

样例输出:


H....
HoLe.
H....
HEL..
HELLO

P....
PAR..
PAR..
PAR..
PAR..
PA.TY
party

H....
H....
HELIX

解题代码:

import java.io.BufferedReader;
 import java.io.IOException;
 import java.io.InputStreamReader;

 public class Main {

     public static void main(String[] args) throws IOException {
         BufferedReader read = new BufferedReader(new InputStreamReader(
                 System.in));
         String s;
         String r;
         int time;
         char[] last;
         StringBuilder temp;
         char[] buff;
         int pos;
         boolean[] used;
         game: while (!(s = read.readLine()).equals("LINGO")) {
             if (s.equals("") || s == null) {
                 continue;
             }
             System.out.println();
             r = s;
             last = new char[] { '.', '.', '.', '.', '.' };
             last[0] = r.charAt(0);
             System.out.println(last);
             time = 1;
             turn: while (!(s = read.readLine()).equals("")) {
                 // check valid
                 if (s.length() != 5) {
                     System.out.println(last);
                     time++;
                     continue turn;
                 }
                 for (int i = 0; i < 5; i++) {
                     if (!Character.isUpperCase(s.charAt(i))) {
                         System.out.println(last);
                         time++;
                         continue turn;
                     }
                 }
                 // is right
                 if (s.equals(r)) {
                     System.out.println(r);
                     over(read);
                     continue game;
                 }
                 if (time == 6) {
                     System.out.println(r.toLowerCase());
                     over(read);
                     continue game;
                 }
                 // check
                 buff = new char[] { '.', '.', '.', '.', '.' };
                 temp = new StringBuilder(r);
                 used = new boolean[5];
                 for (int i = 0; i < 5; i++) {
                     if (r.charAt(i) == s.charAt(i)) {
                         buff[i] = s.charAt(i);
                         temp.setCharAt(i, ' ');
                         used[i] = true;
                     }
                 }
                 for (int i = 0; i < 5; i++) {
                     if (used[i]) {
                         continue;
                     }
                     if ((pos = temp.indexOf(s.charAt(i) + "")) != -1) {
                         buff[i] = Character.toLowerCase(s.charAt(i));
                         temp.setCharAt(pos, ' ');
                         used[i] = true;
                     }
                 }
                 System.out.println(buff);
                 last = buff;
                 time++;
             }
             if (time < 7) {
                 System.out.println(r.toLowerCase());
             }
         }
     }

     public static void over(BufferedReader read) throws IOException {
         while (!read.readLine().equals("")) {
         }
     }
}

  1. 一开始就规定不相邻节点颜色相同,可能得不到最优解。我想个类似的算法,也不确定是否总能得到最优解:先着一个点,随机挑一个相邻点,着第二色,继续随机选一个点,但必须至少有一个边和已着点相邻,着上不同色,当然尽量不增加新色,直到完成。我还找不到反例验证他的错误。。希望LZ也帮想想, 有想法欢迎来邮件。谢谢