首页 > 专题系列 > Java解POJ > POJ 2302 Traditional BINGO [解题报告] Java
2013
11-11

POJ 2302 Traditional BINGO [解题报告] Java

Traditional BINGO

问题描述 :

Traditional BINGO is played in person in a large hall. Players meet at the hall, pay a fee to get in, then the games begin. A night of BINGO consists of many BINGO games played continuously, one after another.

A single BINGO game proceeds like this: Each player has a number of BINGO cards (players can usually play any number of cards). Each BINGO card has 5 rows and 5 columns thus providing 25 spaces.

The columns are labeled from left to right with the letters: ‘B’, ‘I’, ‘N’, ‘G’, ‘O’. With one exception (the center space is “free”) the spaces in the card are assigned values as follows:

  • Each space in the ‘B’ column contains a number from 1 – 15.
  • Each space in the ‘I’ column contains a number from 16 – 30.
  • Each space in the ‘N’ column contains a number from 31 – 45.
  • Each space in the ‘G’ column contains a number from 46 – 60.
  • Each space in the ‘O’ column contains a number from 61 – 75.

Furthermore, a number can appear only once on a single card.

Here’s a sample BINGO card:

BINGO
1017394964
1221365562
1425FREE
SPACE
5270
719325668
524345471


The number of unique BINGO cards is very large and can be calculated with this equation:
// the B, I, G, and O columns * the N column

(15 * 14 * 13 * 12 * 11) ^ 4 * (15 * 14 * 13 * 12)

While perhaps interesting to a statistician, the number of possible BINGO cards has nothing to do with player’s chances of winning.

You will note that there are 75 possible BINGO numbers:

B1, B2, B3, ... B15, I16, I17, I18, ... I30, N31, N32, ... O74, O75.

Each of these numbers is represented by a ball in a large rotating bin. Each ball is painted with its unique BINGO number. An announcer spins the bin, reaches in a selects a ball, and a announces it to the room. The players check all of their cards to see if that number appears on their card. If it is, they mark it. A player may mark the centre FREE SPACE at any time.

When a player has a BINGO (5 marks in a row, column, or diagonal), he or she calls out BINGO. The game pauses while the card is verified. If indeed a winner, the game stops and a new game begins. If the card wasn’t a winner, the game proceeds where it left off. Each BINGO game proceeds until someone wins (there’s always a winner).

输入:

The first line of input contains n, the number of BINGO games that you will analyze. n game descriptions follow. Each game description specifies a card to be played followed by a sequence of BINGO numbers. You are to determine, when the holder of the card will win the game, assuming the player has just this one card and there are no other players.

Each card description consists of five lines, giving the numbers on the card row by row. All but the 3rd row contain 5 numbers; the 3rd contains 4 because of the free space. One or more lines follow that represent some ordering of all 75 bingo numbers. All bingo numbers are simply integers between 1 and 75 – the one-letter prefix is redundant.

输出:

For each game, ouput the line “BINGO after n numbers announced” as appropriate.

Chances of Winning

Every BINGO game has a winning card, so a player’s chances of winning depend on the number of cards in the game and how many cards s/he is playing. For example, if a player has 12 cards in a game with 1200 cards, the chances of winning for that player is 1 in 100.

样例输入:

1
10 17 39 49 64
12 21 36 55 62
14 25 52 70
7 19 32 56 68
5 24 34 54 71
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70
71 72 73 74 75

样例输出:

BINGO after 14 numbers announced

解题代码:

/* @author:zeropinzuo */
import java.io.*;
import java.util.*;

public class Main{
 static Scanner cin;
 public static void main(String args[]){
  cin = new Scanner(System.in);
  int n = cin.nextInt();
  for(int i=0;i< n;i++)
   run();
  }

 static void run(){
   Card card = new Card(cin);
   boolean first=true;
   int n;
   for(int i=0;i< 75;i++){
    n = cin.nextInt();
    if(first==true){
	card.mark(n);
	if(card.check()==true){
	  System.out.println("BINGO after "+(i+1)+" numbers announced");
	  first = false;
	}
    }
   }
 }
}

class Card{
 int[][] map;
 boolean[][] marked;

 public Card(Scanner cin){
  int size=5;
  map = new int[size][size];
  marked = new boolean[size][size];
		
  int i,j;
  for(i=0;i< size;i++)
   for(j=0;j< size;j++){
     marked[i][j] = false;
     if((i!=2)||(j!=2))
	map[i][j] = cin.nextInt();
    }
   marked[2][2] = true;
 }

 void mark(int n){
   int row=0, column=0;

   while(row< 5){
    column=0;
    while(column< 5){
	if(map[row][column]==n){
	  marked[row][column] = true;
	  break;
	}
       column++;
     }

    if(column< 5)
	break;
    row++;
   }
 }

 boolean check(){
   if(checkRow())
	return true;
   else if(checkColumn())
	return true;
   else if(checkDiagonal())
	return true;
  else
	return false;
}

boolean checkRow(){
 int row=0;
 while(row< 5){
   int column=0;
   while(column< 5){
    if(marked[row][column]==false)
        break;
    column++;
   }

  if(column==5){
    break;
   }
   row++;
 }

 if(row< 5){
   return true;
  }
 return false;
}

 boolean checkColumn(){
    int column=0;
    while(column< 5){
	int row=0;
	while(row< 5){
	  if(marked[row][column]==false)
	   break;
	  row++;
	}

	if(row==5)
	  break;
	column++;
    }

    if(column< 5)
	return true;
    return false;
 }


 boolean checkDiagonal(){
   if(checkLeftDiagonal())
     return true;
   else if(checkRightDiagonal())
     return true;
   else
     return false;
  }

 boolean checkLeftDiagonal(){
   int element=0;
   while(element< 5){
     if(marked[element][element] == false)
         return false;
     element++;
   }
   return true;
 }

boolean checkRightDiagonal(){
  int element=0;
  while(element< 5){
   if(marked[element][4-element] == false)
	return false;
   element++;
  }
 return true;
 }
}

  1. #include <cstdio>
    #include <cstring>

    const int MAXSIZE=256;
    //char store[MAXSIZE];
    char str1[MAXSIZE];
    /*
    void init(char *store) {
    int i;
    store['A']=’V', store['B']=’W',store['C']=’X',store['D']=’Y',store['E']=’Z';
    for(i=’F';i<=’Z';++i) store =i-5;
    }
    */
    int main() {
    //freopen("input.txt","r",stdin);
    //init(store);
    char *p;
    while(fgets(str1,MAXSIZE,stdin) && strcmp(str1,"STARTn")==0) {
    if(p=fgets(str1,MAXSIZE,stdin)) {
    for(;*p;++p) {
    //*p=store[*p]
    if(*p<’A’ || *p>’Z') continue;
    if(*p>’E') *p=*p-5;
    else *p=*p+21;
    }
    printf("%s",str1);
    }
    fgets(str1,MAXSIZE,stdin);
    }
    return 0;
    }

  2. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?