首页 > ACM题库 > HDU-杭电 > hdu 2434 Let’s play UNO[解题报告]C++
2014
01-26

hdu 2434 Let’s play UNO[解题报告]C++

Let’s play UNO

问题描述 :

Uno is a famous card game played with a specially printed deck. It’s very
popular as a funny game in a party.
A so-called "official rules" is presented at the Wikipedia, but there are a lot of different extended rules all over the
world according to their specific needs.

      In this problem, you are required to obey our rules introduced below:
      The Uno deck consists of cards of 4 colors: red(R), green(G), blue(B), and yellow(Y).
Each color has two kinds of cards, number cards and action cards.
The ranks in number cards are 0-9. There are 3 "action" cards in each color, labeled "skip"(S), "draw two"(D), and "reverse"(R).
The functions of the actions will be described afterwards.
For each color, there are two copies of each positive number card and action card, but only one zero card, producing 25 cards in total.
      Besides, there are also special black action cards called "wild cards", "wild"(WC) and "wild draw four"(WF).
There are four "wild" and "wild draw four" cards each. Hence, there are 108 cards in total.
      In this problem, a card is marked with an ID of two characters length, the first is the color (R, G, B, Y, W) while the second is the rank (0-9, S, D, R, C, F).
For example, the ID of red 2 is R2, the yellow reverse is YR, the wild cards are WC and WF.
      Supposed there are n players numbered from 1 to n clockwise.
Before playing, players take turns(in the order of 1, 2, … n) to pick seven successive cards from the stock.
The top card of the remaining stock is exposed to start the game, treated as if player 1 dropped that card.
The exposed card will never be WC or WF in this problem.
Then the game begins clockwise (next player is 2), or counter-clockwise (next player is n) if the top exposed card is a reverse.
      At each turn, a player may drop a card from their hand that matches the color or rank of the top exposed card (e.g., if the top card is R3, you can drop R5 or G3;
if the top card is RD, you can drop R3 or GD) or play a WC.
What’s more, if the player has a WF and no other legal cards to drop, he can drop the WF.
Then the card dropped just now becomes the top exposed card.
      If a player has no legal cards, he must draw the top card of the stock and place it in his hand.
After dropping a single card or drawing, the next player clockwise takes a turn, or counter-clockwise when the reverse is in effect.
      When a player drops down to only one card, that player is required to say "uno" to warn other players.
The game ends when a player drops all his/her cards, or the stock is emptied but the current player has to draw a card.
If the last card is an action card, the special effect still occurs.
      When the game ends, all players count the number of points pertaining to the values of the cards in their hands.
Number cards worth the face value on them, colored special cards worth twenty, and wilds worth fifty, e.g., R2 worth 2, G0 worth 0, BD and YS worth 20, WC and WF worth 50.
      The descriptions of the action cards:

      Now here comes the problem.
There are N people playing Uno under the rules mentioned above. Given the sequence of the 108 cards of the stock, you are asked to simulate a Uno game.
      At each turn, the player will always drop a card if permitted.
If there are more than one choices, the player will drop the card with the largest point.
If still a tie, he will choose the one whose ID is the smallest alphabetical order.
      When a player drops WC or WF, he has to name a color.
The first time he will name red, the second time he will name green, the third time blue, the fourth time yellow, the fifth time red again, and so on.
      When the game ends, you should output the final score of each player, and we also want to know how many times each player calls "Uno".

输入:

The first line of the input file contains a single number: the number of test
cases to follow. Each test case has two lines:
The first line contains the number of players N , with 2<=N<=10.
The second line contains 108 IDs of the Uno cards, separated by one space.
Each ID is two characters long as introduced in the description above.

输出:

The first line of the input file contains a single number: the number of test
cases to follow. Each test case has two lines:
The first line contains the number of players N , with 2<=N<=10.
The second line contains 108 IDs of the Uno cards, separated by one space.
Each ID is two characters long as introduced in the description above.

样例输入:

1
2
R9 RD RD RS RS RR RR 
B0 B1 B1 B2 B2 B3 B3 
G0 GD GD GS GS GR GR G9 G9 G8 G8 G7 G7 G6 G6 G5 G5 G4 G4 G3 G3 G2 G2 G1 G1 
Y0 Y9 Y9 Y8 Y8 Y7 Y7 Y6 Y6 Y5 Y5 Y4 Y4 Y3 Y3 Y2 Y2 Y1 Y1 YD YD YS YS YR YR 
R9 R8 R8 R7 R7 R6 R6 R5 R5 R4 R4 R3 R3 R2 R2 R1 R1 R0 
B4 B4 B5 B5 B6 B6 B7 B7 B8 B8 B9 B9 BD BD BS BS BR BR 
WC WC WC WC WF WF WF WF

样例输出:

249 0
0 1
Hint
The process of this game is: G0(exposed) -> B0(Player 2) -> Draw GD(Player 1) -> B3(Player 2) ->Draw GD(Player 1) -> B3(Player 2) -> Draw GS(Player 1) -> B2(Player 2) -> Draw GS(Player 1) -> B2(Player 2) -> Draw GR(Player 1) -> B1, call “Uno”(Player 2) -> Draw GR(Player 1) -> B1(Player 2), end. Score of player 1: 20*12(6 red action cards and 6 green action cards)+9(R9)

/*This Code is Submitted by billforum for Problem 2434 at 2012-01-30 17:11:48*/
#include <iostream>
#include <queue>
#include <memory.h>
using namespace std;

struct point
{
        int length;//朋友的个数
        int step;
        bool visit;
        int f[1001];//存放朋友的号码
        int num;
};

point data[1001];
bool know[1001][1001];//标识两人认识不
int main(int args,char **argv)
{
        int g,n,gn,ntmp,ans=-1;
        int atmp[1001];
        
        while(cin>>g>>n)
        {
                if(g==0&&n==0) break;
//初始化
 for(int i=0;i<n;i++)
                {
                        data[i].length=0;
                        data[i].step=0;
                        data[i].visit=0;
                        data[i].num=i;
                        for(int j=0;j<1001;j++)
                                data[i].f[j]=-1;
                }
                ans=-1;
                for(int i=0;i<1001;i++)
                        for(int j=0;j<1001;j++)
                                know[i][j]=0;
//对输入数据进行处理,构造关系
 for(int i=0;i<g;i++)
                {
                        cin>>gn;
                        for(int j=0;j<gn;j++)
                                cin>>atmp[j];
                        for(int k=0;k<gn;k++)
                        {
                                int t=atmp[k];
                                for(int j=k+1;j<gn;j++)
                                {
                                        int s=atmp[j];
                                        if(!know[t][s])
                                        {
                                        data[t].length++;
                                        data[s].length++;
                                        data[t].f[data[t].length-1]=s;
                                        data[s].f[data[s].length-1]=t;
                                        know[t][s]=1;
                                        know[s][t]=1;
                                        }
                                }
                        }
                }
                queue<point> list;
                data[0].visit=1;
                list.push(data[0]);
                while(!list.empty())
                {
                        point tmp=list.front();
                        if(tmp.num==n-1)
                        {
                                ans=tmp.step;
                                break;
                        }
//广搜
 for(int k=0;k<tmp.length;k++)
                        {
                                int i=tmp.f[k];
                                if(data[i].visit) continue;
                                else
                                {
                                        data[i].visit=1;
                                        data[i].step=tmp.step+1;
                                        list.push(data[i]);
                                }
                        }
                        list.pop();
                }
                if(ans==-1) cout<<"I can never know wywcgs!"<<endl;
                else if(ans==1||ans==0) cout<<"I do know wywcgs!"<<endl;
                else
                {
                        cout<<"I can know wywcgs by at most "<<ans-1<<" person(s)!"<<endl;
                }
                
        }
        
        return 0;
}

 http://acm.hit.edu.cn/hoj/problem/view?id=2434

广搜思想,将每人认识的朋友存在一个变量中,然后在每个搜一遍。

解题转自:http://www.cnblogs.com/wuzhibin/archive/2012/01/30/2332237.html