石子游戏.cpp

编程习题石子游戏的代码

/*
题目 - 石子游戏   
 
描述 
现有4堆石子,两个人轮流取石子,他们有n种可能的取法,取法表示从第1堆取A1个石子,从第2堆中取B1个,第3堆取C1个,第4堆取D1个.如果取的时候某一堆的石子数比所要取的石子数要少,则这种取法是不可行的.取到最后没有可行取法的人就算输了. 
现给出4堆石子的石子数目以及n种取法,请问如果两个人都采用最优取法,先取的人是赢还是输.
 
关于输入 
第一行是4个数,表示每堆石子的数目(石子数目小于等于30). 
第二行是一个正整数n(n<=10),表示取法种数 
接下来n行,每行4个数,表示这种取法会在每一堆石子中取多少个
 
关于输出 
如果先手可以取胜,输出"win",否则输出"lose"
 
例子输入 
5 5 5 5
3
1 1 1 1
1 0 1 0
0 1 0 1

 
例子输出 
win
*/
#include<iostream>
using namespace std;

int n,w[11][4],temp[31][31][31][31];

int judge(int a,int b,int c,int d)
{
	if(a < 0 || b < 0 || c < 0 || d < 0)
		return 1;
	if(temp[a][b][c][d]==-1)
	{
		int count=0;
		for(int i=0;i<n;i++)
			count+=judge(a-w[i][0],b-w[i][1],c-w[i][2],d-w[i][3]);
		if(count!=n)
			temp[a][b][c][d]=1;
		else
			temp[a][b][c][d]=0;
	}
	return temp[a][b][c][d];
}


int main()
{
	int a,b,c,d,i,j,k,t;
	for(i=0;i<31;i++)
		for(j=0;j<31;j++)
			for(k=0;k<31;k++)
				for(t=0;t<31;t++)
					temp[i][j][k][t]=-1;
	cin>>a>>b>>c>>d>>n;
	for(i=0;i<n;i++)
		cin>>w[i][0]>>w[i][1]>>w[i][2]>>w[i][3];
	if(judge(a,b,c,d))
		cout<<"win"<<endl;
	else
		cout<<"lose"<<endl;
	return 0;
}