USACO搜索練習題 Cow Yahtzee [cowyotz]

Cow Yahtzee  [USACO 2006-2007 Feb07]

In their usual clumsy way, the cows are play a version of Yahtzee,
the dice-rolling game.  They roll N (1 <= N <= 20) dice, each having
S (1 <= S <= 8) sides.  They are curious as to the number of ways
a dice roll can meet a particular criterion (like "contains three
2's" or "contains one 2 and two 3's").

Help them learn about probability. Write a program that reads not
only N and S but also some expressions that describe their criteria.
Count the number ways the expression can be satisfied over the
entire set of all possible dice rolls (the entire set of rolls for
three two-sided dice is: {1,1,1; 1,1,2; 1,2,1; 1,2,2; 2,1,1; 2,1,2;
2,2,1; 2,2,2};

Expressions comprise combinations of a basic form that expresses
the thought "want at least W copies of result R". It looks like this:

WxR

where (0 <= W <= N and 1 <= R <= S). Each test run will supply E
expressions (1 <= E <= 20), each of which contains a number 1..10
of the basic forms separated by a '+', which means 'and' (see below).
The set of lines expresses the thought that is the 'inclusive or'
of each of the lines individually. Thus the pair of expressions
shown below means "at least three rolls of five OR both at least
one roll of 3 and also at least two rolls of 4":

3x5
1x3+2x4

Here are some of the combinations of four five-sided dice that
satisfy the above expression: 5,5,5,1; 4,5,5,5; 3,4,4,2; 3,4,4,3;
3,4,4,5; 4,4,5,3.

Programming note: Be sure to verify that you can read in two integers
from one line and a string from the next line. In some languages'
I/O schema, this is harder than it looks!

Also note that the total number of dice combinations will never
exceed 1,512,768 in the supplied test data.

PROBLEM NAME: cowyotz

INPUT FORMAT:

* Line 1: Three space-separated integers: N, S, and E

* Lines 2..E+1: Line i+1 describes expression i as above.

SAMPLE INPUT (file cowyotz.in):

4 5 2
3x5
1x3+2x4

INPUT DETAILS:

This is the encoding of the expression used as an example in the task text.

OUTPUT FORMAT:

* Line 1: A single integer that is the number of ways the
        expression(s) can be satisfied by rolling the dice in all
        combinations.

SAMPLE OUTPUT (file cowyotz.out):

63

OUTPUT DETAILS:

63 rolls satisfy the expression.

【分析】 

這是一道不算太難也不算太簡單的搜索題目，本題的難點有3個：

1.讀入骰子規則時對字符串的處理；

2.運用搜索解決排列組合問題；

3.判斷每種 骰子的結果是否符合規則。

我做這個題的時候使用了廣度優先搜索（=寬度優先搜索），結果是AEAAAAAAWA，80分；

我的一位同學(paulinsider@gmail.com)做的時候使用了深度優先搜索，即遞歸求解排列

組合。沒想到，他竟然全過，拿了100分！了不起啊！

【代碼】

<1>我的代碼  
AEAAAAAAWA ，80分  （A=結果正確，E=運行時出錯，W=結果錯誤）

 #include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
int N,S,E;
int r=0;
int Total=0;
class Rules
{
public:
 int num;
 int Num[100];
 int Up[100];
 Rules()
 {
  num=0;
  for (int i=0;i<=99;i++)
  {
   Num[i]=0;
   Up[i]=0;
  }
 }
}R[1000];

void init()
{
 cin>>N>>S>>E;
 char str[1000];
 for (int i=1;i<=E;i++)
 {
  r++;
  for (int j=0;j<=999;j++) str[j]='\0';
  cin>>str;
  int len=strlen(str);
  int p=0;
  int n1=0;
  int n2=0;
  int nt=0;
  bool flag=true;
  while (p<len)
  {
   if(str[p]>='0' && str[p]<='9')
   {
    nt=nt*10+str[p]-'0';
    p++;
    continue;
   } 
   else
   {
    if (flag)
    {
     n1=nt;
     nt=0;
    }
    if (!flag)
    {
     n2=nt;
     nt=0;
    }
    
    if (str[p]=='x')
    {
     R[r].Num[R[r].num]=n1;
     flag=!flag;
     p++;
     continue;
    }
    if (str[p]=='+')
    {
     R[r].Up[R[r].num]=n2;
     flag=!flag;
     p++;
     R[r].num++;
     continue;
    }
   } 
  }
  n2=nt;
  R[r].Up[R[r].num]=n2;
  R[r].num++;
 }
}
void debug()
{
 cout<<r<<endl;
 for (int i=1;i<=r;i++)
 {
  for (int j=0;j<R[i].num;j++)
   cout<<i<<" "<<j<<" "<<R[i].Num[j]<<" "<<R[i].Up[j]<<endl;
 }
}

class QUEUE
{
public:
 int Nu;
 int Touzi[9];
 QUEUE()
 {
  Nu=0;
  for (int i=0;i<=9;i++)
   Touzi[i]=0;
 }
};
QUEUE Q[2000000];

void check(int x)
{
 int Want[10]={0};
 for (int i=1;i<=N;i++)
 {
  Want[Q[x].Touzi[i]]++;
 }
 
 bool yes;
 for (int i=1;i<=r;i++)
 {
  for (int j=0;j<R[i].num;j++)
  {
   yes=true;
   if ( Want[R[i].Up[j]]< R[i].Num[j])
   {
    yes=false;
    break;
   }
  } 
  if(yes) 
  {
   Total++;
   return;
  }
 }
}

void BFS()
{
 int big=1;
 int small=0;
 Q[0].Nu=0;
 while(small<big)
 {
  int TN=Q[small].Nu;
  if (TN==N)
  {
   check(small);
   small++;
   continue;
  }
  int Need=TN+1;
  for (int i=1;i<=S;i++)
  {
   for (int k=0;k<=TN;k++) 
    Q[big].Touzi[k]=Q[small].Touzi[k];
   Q[big].Nu=Need;   
   Q[big].Touzi[Need]=i;
   big++;
  }
  small++;
 }
}

int main()
{
 freopen("cowyotz.in","r",stdin);
 freopen("cowyotz.out","w",stdout);
 init();
 BFS();
 cout<<Total<<endl;
 return 0;
}

<2>我同學的代碼

AAAAAAAAAA，100分 （A=結果正確）

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
int number,m,n,q[1512770][9],ji=0,ji1=0,c=0,f[20][9],used[9]={0},answer=0;
bool check(int x);
void di(int x);
int main()
{
 freopen ("cowyotz.in","r",stdin);
 freopen ("cowyotz.out","w",stdout);
 scanf("%d%d%d\n",&number,&m,&n);
 di(1);
 for (int i=0;i<n;i++)
 {
  char s[50];
  cin>>s;
  int lq;
  lq=strlen(s);
  int j=0;
  while (j<lq)
  {
   int a,b;
   a=s[j]-'0';
   b=s[j+2]-'0';
   f[ji1][b]=a;
   if (s[j+3]=='+')
   {
    j+=4;
   }
   else
   {
    break;
   }
  }
  ji1++;
 }
 for (int o=0;o<ji;o++)
 {
  int u[9]={0};
  for (int i=1;i<=number;i++)
  {
   u[q[o][i]]++;
  }
  for (int i=1;i<=m;i++)
  {
   q[o][i]=u[i];
  }
  if (check(o))
  {
   answer++;
  }
 }
 printf("%d",answer);
 return 0;
}
void di(int x)
{
 q[ji][c]=x;
 if (c==number)
 {
  ji++;
  for (int i=1;i<=number;i++)
  {
   q[ji][i]=q[ji-1][i];
  }
  
 }
 else
 {
  for (int i=1;i<=m;i++)
  {
   c++;
   di(i);
   c--;
  }
 }
}
bool check(int x)
{
 int p=0;
 for (int j=0;j<n;j++)
 {
  p=0;
  for (int i=1;i<=m;i++)
  {
   if (f[j][i]==0)
   {
    continue;
   }
   if (q[x][i]<f[j][i])
   {
    p++;
    break;
   }
  }
  if (p==0)
  {
   return true;
  }
 }
 return false;
}