首页 > 数据结构 > Hash表 > POJ 1786 Bridge Hands [解题报告] Java
2013
11-10

POJ 1786 Bridge Hands [解题报告] Java

Bridge Hands

问题描述 :

Drivers of Advanced Cargo Movement, Ltd. usually have to wait quite a long time when waiting at border crossings for duty clearance. They are used to play various (card) games to have some fun. One of the games is Bridge. Playing Bridge involves dealing a standard deck of 52 cards to 4 players, so that each player receives 13 cards. Good players can then play with the hand as it is dealt, but most ordinary players will need to sort it, firstly by suit and then by rank within suit. There is no fixed ranking of the suits for this purpose, but it is useful to alternate the colors, so we will presume the following ordering: (club) < (diamond) < (spade) < (heart). (Note that because most character sets do not recognize these symbols, from now on we will use the more conventional C, D, S, and H). Within a suit, Ace is high, so the ordering is

2 < 3 < 4 < 5 < 6 < 7 < 8 < 9 < T < J < Q < K < A .

The players are usually called North, South, East, and West as they sit at the points of the compass. One player is designated the dealer and she deals one card to each player starting with the player on her left and proceeding clockwise until she deals the last card to herself.

Write a program that will read in a representation of a deck of cards, deal them, sort them, and then display four sorted hands in the format shown below.

输入:

The input consists of a series of deals. Each deal begins with a line containing a single letter representing the dealer (“N”, “E”, “S”, “W”) followed by two lines representing the deck, card by card, as shown below. The first card given in the input is the first one to be dealt. The file is be terminated by a line consisting of a single hash character (“#”).

输出:

Output should consist of a series of sets of 24 lines, one set for each deal, separated by blank lines. Each set will consist of four groups of six lines displaying the sorted hands, in the order of their suit and rank. Use the format shown below. South player always goes first.

样例输入:

N
CQDTC4D8S7HTDAH7D2S3D6C6S6D9S4SAD7H2CKH5D3CTS8C9H3C3
DQS9SQDJH8HAS2SKD4H4S5C7SJC8DKC5C2CAHQCJSTH6HKH9D5HJ
#

样例输出:

South player:
+---+---+---+---+---+---+---+---+---+---+---+---+---+
|3 3|5 5|7 7|T T|J J|9 9|T T|J J|3 3|K K|2 2|9 9|T T|
| C | C | C | C | C | D | D | D | S | S | H | H | H |
|3 3|5 5|7 7|T T|J J|9 9|T T|J J|3 3|K K|2 2|9 9|T T|
+---+---+---+---+---+---+---+---+---+---+---+---+---+
West player:
+---+---+---+---+---+---+---+---+---+---+---+---+---+
|2 2|4 4|K K|4 4|5 5|6 6|Q Q|A A|4 4|8 8|T T|J J|8 8|
| C | C | C | D | D | D | D | D | S | S | S | S | H |
|2 2|4 4|K K|4 4|5 5|6 6|Q Q|A A|4 4|8 8|T T|J J|8 8|
+---+---+---+---+---+---+---+---+---+---+---+---+---+
North player:
+---+---+---+---+---+---+---+---+---+---+---+---+---+
|6 6|8 8|9 9|A A|8 8|9 9|A A|4 4|5 5|6 6|7 7|J J|A A|
| C | C | C | C | D | S | S | H | H | H | H | H | H |
|6 6|8 8|9 9|A A|8 8|9 9|A A|4 4|5 5|6 6|7 7|J J|A A|
+---+---+---+---+---+---+---+---+---+---+---+---+---+
East player:
+---+---+---+---+---+---+---+---+---+---+---+---+---+
|Q Q|2 2|3 3|7 7|K K|2 2|5 5|6 6|7 7|Q Q|3 3|Q Q|K K|
| C | D | D | D | D | S | S | S | S | S | H | H | H |
|Q Q|2 2|3 3|7 7|K K|2 2|5 5|6 6|7 7|Q Q|3 3|Q Q|K K|
+---+---+---+---+---+---+---+---+---+---+---+---+---+

解题代码:

//* @author: SmilingWang
import java.util.*;

public class Main {
  public static void main(String[] args){
    Scanner in = new Scanner(System.in);
    Map< String, Integer> map = new HashMap< String, Integer>();
    map.put("N", 0);
    map.put("E", 1);
    map.put("S", 2);
    map.put("W", 3);
    String pos[] = {"N", "E", "S", "W"};
    while(true){
	String dealer = in.next();
	String table[] = new String[4];
	for(int i = 0; i < 4; i++){
		table[i] = "";
	}
	if(dealer.equals("#")){
		return;
	}
	String card = "";
	card += in.next();
	card += in.next();
	
	//System.out.println(card);
	int count = 0;
	int turn = (map.get(dealer) + 1) % 4;
	while(count < 104){
		table[turn] += (card.charAt(count) +""+ card.charAt(count+1));
		count += 2;
		turn = (turn + 1) % 4;
	}
	//System.out.println(card.length());
	//System.out.println(Arrays.toString(table));
	Card cards[][] = new Card[4][13];
	for(int t = 0; t < 4; t++){
		cards[t] = new Card[13];
		for(int i = 0, j = 0; i < 13; i++, j += 2){
			cards[t][i] = Card.read(table[t].charAt(j), table[t].charAt(j+1));
		}
		Arrays.sort(cards[t]);
	}
	System.out.println("South player:");
	System.out.println("+---+---+---+---+---+---+---+---+---+---+---+---+---+");
	for(int i = 0; i < 13; i++){
		System.out.print("|" + cards[2][i].code + " " + cards[2][i].code);
	}
	System.out.println("|");
	for(int i = 0; i < 13; i++){
		System.out.print("| " + cards[2][i].cc + " ");
	}
	System.out.println("|");
	for(int i = 0; i < 13; i++){
		System.out.print("|" + cards[2][i].code + " " + cards[2][i].code);
	}
	System.out.println("|");
	System.out.println("+---+---+---+---+---+---+---+---+---+---+---+---+---+");
	
	System.out.println("West player:");
	System.out.println("+---+---+---+---+---+---+---+---+---+---+---+---+---+");
	for(int i = 0; i < 13; i++){
		System.out.print("|" + cards[3][i].code + " " + cards[3][i].code);
	}
	System.out.println("|");
	for(int i = 0; i < 13; i++){
		System.out.print("| " + cards[3][i].cc + " ");
	}
	System.out.println("|");
	for(int i = 0; i < 13; i++){
		System.out.print("|" + cards[3][i].code + " " + cards[3][i].code);
	}
	System.out.println("|");
	System.out.println("+---+---+---+---+---+---+---+---+---+---+---+---+---+");
	
	System.out.println("North player:");
	System.out.println("+---+---+---+---+---+---+---+---+---+---+---+---+---+");
	for(int i = 0; i < 13; i++){
		System.out.print("|" + cards[0][i].code + " " + cards[0][i].code);
	}
	System.out.println("|");
	for(int i = 0; i < 13; i++){
		System.out.print("| " + cards[0][i].cc + " ");
	}
	System.out.println("|");
	for(int i = 0; i < 13; i++){
		System.out.print("|" + cards[0][i].code + " " + cards[0][i].code);
	}
	System.out.println("|");
	System.out.println("+---+---+---+---+---+---+---+---+---+---+---+---+---+");
	System.out.println("East player:");
	System.out.println("+---+---+---+---+---+---+---+---+---+---+---+---+---+");
	for(int i = 0; i < 13; i++){
		System.out.print("|" + cards[1][i].code + " " + cards[1][i].code);
	}
	System.out.println("|");
	for(int i = 0; i < 13; i++){
		System.out.print("| " + cards[1][i].cc + " ");
	}
	System.out.println("|");
	for(int i = 0; i < 13; i++){
		System.out.print("|" + cards[1][i].code + " " + cards[1][i].code);
	}
	System.out.println("|");
	System.out.println("+---+---+---+---+---+---+---+---+---+---+---+---+---+");
	System.out.println();
	}
   }
}

class Card implements Comparable{
  int color;
  int num;
  char code;
  char cc;
  public Card(int c, int n, char code, char cc){
	color = c;
	num = n;
	this.code = code;
	this.cc = cc;
}
public static Card read(char c, char n){
	int color = -1;
	int num = 0;
	if(c == 'C'){
		color = 0;
	}
	else if(c == 'D'){
		color = 1;
	}
	else if(c == 'S'){
		color = 2;
	}
	else if(c == 'H'){
		color = 3;
	}
	if(Character.isLetter(n)){
		if(n == 'A'){
			num = 14;
		}
		else if(n == 'T'){
			num = 10;
       	}
		else if(n == 'J'){
			num = 11;
		}
		else if(n == 'Q'){
			num = 12;
		}
		else if(n == 'K'){
			num = 13;
		}
	}
	else{
		num = n - '0';
	}
	return new Card(color, num, n, c);
    }
	
    public int compareTo(Card rhs){
	if(this.color != rhs.color){
		return this.color - rhs.color;
	}
	else{
		return this.num - rhs.num;
	}
    }
	
    public String toString(){
	return num + " " + color + " " + code + " " ;
    }
}

  1. 有限自动机在ACM中是必须掌握的算法,实际上在面试当中几乎不可能让你单独的去实现这个算法,如果有题目要用到有限自动机来降低时间复杂度,那么这种面试题应该属于很难的级别了。

  2. int half(int *array,int len,int key)
    {
    int l=0,r=len;
    while(l<r)
    {
    int m=(l+r)>>1;
    if(key>array )l=m+1;
    else if(key<array )r=m;
    else return m;
    }
    return -1;
    }
    这种就能避免一些Bug
    l,m,r
    左边是l,m;右边就是m+1,r;