首页 > 专题系列 > Java解POJ > POJ 2035 Hit or Miss [解题报告] Java
2013
11-10

POJ 2035 Hit or Miss [解题报告] Java

Hit or Miss

问题描述 :

One very simple type of solitaire game known as “Hit or Miss” (also known as “Frustration,” “Harvest,” “Roll-Call,” “Talkative”, and “Treize”) is played as follows: take a standard deck of 52 playing cards — four sets of cards numbered 1 through 13 (suits do not matter in this game) which have been shuffled — and start counting through the deck 1, 2, 3, . . . , and so on. When your count reaches 13, start over at 1. Each time you count, look at the top card of the deck and do one of two things: if the number you count matches the value of the top card, discard it from the deck; if it does not match it, move that card to the bottom of the deck. You win the game if you are able to remove all cards from the deck (which may take a very long time).

A version of this game can be devised for two or more players. The first player starts as before with a 52 card deck, while the other players have no cards initially. As the first player removes cards from her deck, she gives them to the second player, who then starts playing the same game, starting at count 1. When that player gets a match, he passes his card to the third player, and so on. The last player discards matches rather than passing them to player 1. All players who have cards to play with perform the following 2-step cycle of moves in lockstep:

1. Each player says his or her current count value and checks for a match. If there is no match, the top card is moved to the bottom of the deck; otherwise it is passed to the next player (or discarded if this is the last player).

2. Each player except the first takes a passed card (if there is one) and places it at the bottom of his or her deck.

These rules are repeated over and over until either the game is won (all the cards are discarded by the last player) or an unwinnable position is reached. If any player ever runs out of cards, he waits until he is passed a card and resumes his count from where he left off. (e.g., if player 3 passes his last card on a count of 7, he waits until he receives a card from player 2 and resumes his count with 8 at the beginning of the next 2-step cycle).

输入:

Input will consist of multiple input sets. The first line of the file will contain a single positive integer nindicating the number of input sets in the file. Each input set will be a single line containing 53 integers: the first integer will indicate the number of players in the game and the remaining 52 values will be the initial layout of the cards in the deck, topmost card first. These values will all lie in the range 1 . . . 13, and the number of players will lie in the range 1. . . 10.

输出:

For each input set, output the input set number (as shown below, starting with 1) and either the phrase “unwinnable” or a list showing the last card discarded by each player. Use a single blank to separate all outputs.

样例输入:

2
4 1 2 3 4 5 6 7 8 9 10 11 12 13 1 2 3 4 5 6 7 8 9 10 11 12 13 1 2 3 4 5 6 7 8 9 10 11 12 13 1 2 3 4 5 6 7 8 9 10 11 12 13
4 2 3 4 5 6 7 8 9 10 11 12 13 1 2 3 4 5 6 7 8 9 10 11 12 13 1 2 3 4 5 6 7 8 9 10 11 12 13 1 2 3 4 5 6 7 8 9 10 11 12 13 1

样例输出:

Case 1: 13 13 13 13
Case 2: unwinnable

解题代码:

/* @author: */
import java.util.Scanner;
import java.util.Arrays;
public class Main{
 
 public static void main(String args[])
{
 Scanner sc=new Scanner(System.in);
 
    int c[][]=new int[11][53],p[]=new int[11],r[]=new int[2],d[]=new int[11],count[]=new int[11];
    int casen,i,j,k,pn,top,discard,noanswer;
    casen=sc.nextInt();
    for(k=1;k<=casen;k++)
    {
      pn=sc.nextInt();
      for(i=0;i< pn;i++){count[i]=c[i][0]=0;p[i]=1;}
      c[0][0]=52;top=0;noanswer=0;r[0]=r[1]=0;
      for(i=1;i<=52;i++)
        c[0][i]=sc.nextInt();
      while(top< pn&&c[top][0]!=0)
      {
        if(noanswer!=0)break;
        discard=0;
        for(i=0;i< pn;i++)
        {
           if(discard!=0){
                 
            for(j=c[i][0];j>=p[i];j--)c[i][j+1]=c[i][j];
            c[i][0]++;
            c[i][p[i]]=discard;
            p[i]++;if(p[i]>c[i][0])p[i]=1;
        }    
        discard=0;
       if(c[i][0]!=0){                    
           count[i]++;if(count[i]>13)count[i]=1;
       if(c[i][p[i]]==count[i])
       {
       discard=count[i];if(top==i)r[1]=0;
       for(j=p[i];j< c[i][0];j++)c[i][j]=c[i][j+1];
       c[i][0]--;p[i]--;
       if(c[i][0]==0)d[i]=count[i];
       if(top==i&&c[i][0]==0)top++;
       }    
          else if(top==i&&r[1]==0){r[0]=p[i];r[1]=count[i];} 
          else if(top==i&&r[0]==p[i]&&r[1]==count[i])
             {noanswer=1;break;}  
          p[i]++;if(p[i]>c[i][0])p[i]=1;
      }    
     }    
   }    
   System.out.printf("Case %d:",k);
   if(noanswer!=0) System.out.printf(" unwinnable\n");
   else {
         for(i=0;i< pn;i++) System.out.printf(" %d",d[i]);
         System.out.printf("\n");
        }    
    }      
  }
}

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

  2. 嗯 分析得很到位,确实用模板编程能让面试官对你的印象更好。在设置辅助栈的时候可以这样:push时,比较要push的elem和辅助栈的栈顶,elem<=min.top(),则min.push(elem).否则只要push(elem)就好。在pop的时候,比较stack.top()与min.top(),if(stack.top()<=min.top()),则{stack.pop();min.pop();},否则{stack.pop();}.