首页 > ACM题库 > HDU-杭电 > HDU 4470-Blackjack-枚举-[解题报告]HOJ
2015
07-16

HDU 4470-Blackjack-枚举-[解题报告]HOJ

Blackjack

问题描述 :

You, as a great mathematician and a former member of Blackjack Team, are recently declared “unwelcome person” by managers of local casinos. Extremely bored, you reminded of your life forming a team beating casinos at blackjack worldwide, and decided to help your friends in winning blackjack games.
Blackjack, also known as twenty-one, is a game frequently seen in casinos, played with one deck, or several decks of 52 cards. The version your friend plays is slightly different from what we used to see in usual casinos. In this version, the game is played between a player and a dealer with a deck of n cards, namely a1, a2, . . . , an, instead of regular decks of 52 cards in standard version. The ith card has the unique numeric value ai, which is important in following description of rules.
The game is played in several rounds as long as not less than k (k ≥ 10) cards left in the deck. Cards are dealt from a1 to an, while each card is dealt out at most once. In each round, the player is dealt one card, then the dealer, then the player, then dealer. They now have two cards in their hand respectively. Then the player would keep on taking a hit until he busts (total value of his hand exceeds 21 points) or he feels it’s enough (total value of his hand exceeds 15 points) or he has taken 3 hits already. He immediately loses the round if he busts. If he has taken 3 hits without bust, making his hand consist of 5 cards, he wins the round, ending the round right away. Then the dealer will use the exactly same strategy as the player. Of course, the dealer loses the round immediately if he busts, wins the round at once if his hand consists of 5 cards, with the same rule applying. If after taking hits neither the player nor the dealer wins or loses, sums of points (described below) in their hands will be compared, and the person with larger one will win the round. In case of tie, neither wins or loses. Of course, this ends the current round.
In the casino your friend plays, there is a special rule: before the game starts, the player is required to cut the deck of card exactly once. By saying cut the deck we mean to change deck of cards from
a1, a2, . . . , an
to
ap, ap+1, . . . ; aq, a1, a2, . . . , ap-1, aq+1, . . . , an(1 < p ≤ q < n)
With your super power (in hacking) you now know the deck of cards to play. Now you want to instruct your friend to cut the cards by telling your friend p and q in a secret manner, in order to maximize number of rounds he wins.

输入:

There are several test cases.
For each test case, the first line contains two integers, namely n (20 ≤ n ≤ 2000) and k (10 ≤ k ≤ n).
The following lines contain totally n characters separated by spaces or line breaks. Characters can be any of A,2,3,4,5,6,7,8,T,J,Q,K where A stands for numeric 1 and T,J,Q,K stands for numeric 10.
Input is terminated by EOF.

输出:

There are several test cases.
For each test case, the first line contains two integers, namely n (20 ≤ n ≤ 2000) and k (10 ≤ k ≤ n).
The following lines contain totally n characters separated by spaces or line breaks. Characters can be any of A,2,3,4,5,6,7,8,T,J,Q,K where A stands for numeric 1 and T,J,Q,K stands for numeric 10.
Input is terminated by EOF.

样例输入:

20 10
8 4 7 8 8 K 5 A Q Q A Q 6 4 J 6 9 5
3 9
40 10
3 J 7 7 2 T J 6 A 4 4 8 J T 6 A 6 2 K 9
6 5 7 J T 3 5 5 3 7 7 J 5 3 A 5 9 Q 6 7

样例输出:

Case 1: 3
Case 2: 6

这道题一开始看上去枚举就可以了,但是最后发现一共有12种情况,开始没数齐。最后怎么交都是WA,最后发现边界没处理,好吧,我也懒得弄了,先放在这。

#include<stdio.h>
#include<string>
#include<sstream>
#include<math.h>
#include<string.h>
#include<iostream>
using namespace std;
int grid[201][201],is_legal[201][201];
int main()
{
    int n,m;
    while(cin>>n>>m && n && m)
    {
        memset(grid,0,sizeof(grid));
        memset(is_legal,0,sizeof(is_legal));
        char temp;int flag = 1;
        for(int i = 0;i < n;i++)
            for(int j = 0;j < m;j++)
            {
                cin>>temp;
                if(temp == '#') {grid[i][j] = 1;is_legal[i][j] = 1;}
                if(temp == '.') {grid[i][j] = 0;is_legal[i][j] = 0;}
            }
        int sum = 0;
        for(int i = 0;i < n;i++)
            for(int j = 0;j < m;j++)
            {
                int flagt = 0;
                if(i != n - 1 && j != m - 1)
                {
                    if(!grid[i][j] && !grid[i][j + 1] && !grid[i + 1][j + 1] && (!is_legal[i][j] || !is_legal[i][j + 1] && !is_legal[i + 1][j + 1]))
                    {
                        is_legal[i][j] = 1;is_legal[i][j + 1] = 1;is_legal[i + 1][j + 1] = 1;
                        sum++;flagt = 1;
                    }
                    else if(!grid[i][j] && !grid[i][j + 1] && !grid[i + 1][j] && (!is_legal[i][j] || !is_legal[i][j + 1] && !is_legal[i + 1][j]))
                    {
                        is_legal[i][j] = 1;is_legal[i][j + 1] = 1;is_legal[i + 1][j] = 1;
                        sum++;flagt = 1;
                    }
                    else if(!grid[i][j] && !grid[i + 1][j] && !grid[i + 1][j + 1] && (!is_legal[i][j] || !is_legal[i + 1][j] && !is_legal[i + 1][j + 1]))
                    {
                        is_legal[i][j] = 1;is_legal[i + 1][j] = 1;is_legal[i + 1][j + 1] = 1;
                        sum++;flagt = 1;
                    }
                }
                if(i != n - 1 && j != 0)
                {
                    if(!grid[i][j] && !grid[i + 1][j - 1] && !grid[i + 1][j] && (!is_legal[i][j] || !is_legal[i + 1][j - 1] && !is_legal[i + 1][j]))
                    {
                        is_legal[i][j] = 1;is_legal[i + 1][j - 1] = 1;is_legal[i + 1][j] = 1;
                        sum++;flagt = 1;
                    }
                    else if(!grid[i][j] && !grid[i][j - 1] && !grid[i + 1][j] && (!is_legal[i][j] || !is_legal[i][j - 1] && !is_legal[i + 1][j]))
                    {
                        is_legal[i][j] = 1;is_legal[i][j - 1] = 1;is_legal[i + 1][j] = 1;
                        sum++;flagt = 1;
                    }
                    else if(!grid[i][j] && !grid[i][j - 1] && !grid[i + 1][j - 1] && (!is_legal[i][j] || !is_legal[i][j - 1] && !is_legal[i + 1][j - 1]))
                    {
                        is_legal[i][j] = 1;is_legal[i][j - 1] = 1;is_legal[i + 1][j - 1] = 1;
                        sum++;flagt = 1;
                    }
                }
                if(i != 0 && j != m - 1)
                {
                    if(!grid[i][j] && !grid[i - 1][j] && !grid[i][j + 1] && (!is_legal[i][j] || !is_legal[i - 1][j] && !is_legal[i][j + 1]))
                    {
                        is_legal[i][j] = 1;is_legal[i - 1][j] = 1;is_legal[i][j + 1] = 1;
                        sum++;flagt = 1;
                    }
                    else if(!grid[i][j] && !grid[i - 1][j] && !grid[i - 1][j + 1] && (!is_legal[i][j] || !is_legal[i - 1][j] && !is_legal[i - 1][j + 1]))
                    {
                        is_legal[i][j] = 1;is_legal[i - 1][j] = 1;is_legal[i - 1][j + 1] = 1;
                        sum++;flagt = 1;
                    }
                    else if(!grid[i][j] && !grid[i][j + 1] && !grid[i - 1][j + 1] && (!is_legal[i][j] || !is_legal[i][j + 1] && !is_legal[i - 1][j + 1]))
                    {
                        is_legal[i][j] = 1;is_legal[i][j + 1] = 1;is_legal[i - 1][j + 1] = 1;
                        sum++;flagt = 1;
                    }
                }
                if(i != 0 && j != 0)
                {
                    if(!grid[i][j] && !grid[i - 1][j] && !grid[i - 1][j  - 1] && (!is_legal[i][j] || !is_legal[i - 1][j] && !is_legal[i - 1][j - 1]))
                    {
                        is_legal[i][j] = 1;is_legal[i - 1][j] = 1;is_legal[i - 1][j - 1] = 1;
                        sum++;flagt = 1;
                    }
                    else if(!grid[i][j] && !grid[i][j - 1] && !grid[i - 1][j  - 1] && (!is_legal[i][j] || !is_legal[i][j - 1] && !is_legal[i - 1][j - 1]))
                    {
                        is_legal[i][j] = 1;is_legal[i][j - 1] = 1;is_legal[i - 1][j - 1] = 1;
                        sum++;flagt = 1;
                    }
                    else if(!grid[i][j] && !grid[i][j - 1] && !grid[i - 1][j] && (!is_legal[i][j] || !is_legal[i][j - 1] && !is_legal[i - 1][j]))
                    {
                        is_legal[i][j] = 1;is_legal[i][j - 1] = 1;is_legal[i - 1][j] = 1;
                        sum++;flagt = 1;
                    }
                }
                if(!flagt && !is_legal[i][j]) {flag = 0;break;}  //一开始没判断这里,没及时退出,会出错
            }
            int wandan = 0;
            if(wandan || !flag) printf("-1\n");
            else printf("%d\n",sum);
    }
    return 0;
}

未通过的数据(边界没处理好):

4 4 
.##. 
..#. 
..#. 
..#. 
2 4 
.##. 
#### 

2 4 
.### 
#### 



版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/glqglqglq2/article/details/38612439