斗地主
题目描述
众所周知,小 X 是一个身材极好、英俊潇洒、十分贪玩成绩却依然很好的奆老。
这不,他又找了他的几个好基友去他家里玩斗地主了……
身为奆老的小 X 一向认为身边人和自己一样的厉害,他坚信你和他一样有未卜先知的能力,他在他们玩完斗地主后,告诉了你他们的最终得分,希望你猜出他们最少玩了几局牌?
注意:小 X 他们至少玩了 1 局斗地主。
以下是斗地主的规则:发完牌后三人依次叫牌,可叫 1 分、2 分、3 分或不叫,所叫的分数称为底分,分数叫的高赢的多,输的也多。叫完后叫分最高者为地主,然后开始打牌,若地主获胜则地主得到 2 倍的底分,其余两家农民各输掉一份底分;若地主输了则地主输掉2 倍的底分,其余两家农民各赢得一份底分。
这不,他又找了他的几个好基友去他家里玩斗地主了……
身为奆老的小 X 一向认为身边人和自己一样的厉害,他坚信你和他一样有未卜先知的能力,他在他们玩完斗地主后,告诉了你他们的最终得分,希望你猜出他们最少玩了几局牌?
注意:小 X 他们至少玩了 1 局斗地主。
以下是斗地主的规则:发完牌后三人依次叫牌,可叫 1 分、2 分、3 分或不叫,所叫的分数称为底分,分数叫的高赢的多,输的也多。叫完后叫分最高者为地主,然后开始打牌,若地主获胜则地主得到 2 倍的底分,其余两家农民各输掉一份底分;若地主输了则地主输掉2 倍的底分,其余两家农民各赢得一份底分。
输入
输入数据仅有一行包含四个用空格隔开的整数 n,a,b,c,分别表示小 X 他们玩了不超过n 局斗地主,最终三人的得分分别为 a,b,c
输出
输出一行一个整数表示最少打了几付牌,若这个得分在 n 付牌内不可能出现,则输出-1
样例输入
5 0 0 0
样例输出
2
提示
开始时 3 人得分均为 0 分,第一副牌小 X 做了 3 分地主获胜,3 人得分变为 6,-3,-3,第二副牌小 X 继续做了 3 分地主失败,3 人得分归 0,符合输入要求,牌局结束。
对于 30%的数据,n<=5
对于另外 20%的数据,a,b,c 中有两个数相等
对于 100%的数据,n<=100,-300<=a,b,c<=300,a+b+c=0
【题解】
由于A+B+C = 0 ,其实我们枚举两个人就行了,然后每个人可以当地主,每次可以选择3种底分,还有输赢2种情况。所以所有的情况有 3 * 3 * 2 = 18 种情况。
利用BFS进行搜索即可。
注意细节有:1、可能为负数所以可以加一个偏移量使它变正。
2、搜索两个维度即可,第三个是固定的。
3、如果三个人都为0,特判 打了多少局,如果大于等于2,答案就是2,否则就是-1.
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N = 1200 ; 4 const int M = 600 ; 5 int p[] = { 6 2,-2,-1,1,-1,1, 7 4,-4,-2,2,-2,2, 8 6,-6,-3,3,-3,3 9 }; 10 int q[] = { 11 -1,1,2,-2,-1,1, 12 -2,2,4,-4,-2,2, 13 -3,3,6,-6,-3,3 14 }; 15 typedef struct Node{ 16 int x,y, step; 17 }Node; 18 int n,a,b,c; 19 int vis[N+5][N+5]; 20 void BFS( ){ 21 queue<Node>Q; 22 Q.push( Node{0,0,0} ); 23 24 vis[M][M] = 1 ; 25 while( !Q.empty() ){ 26 Node cur = Q.front(); 27 Q.pop(); 28 int A = cur.x ; 29 int B = cur.y ; 30 int C = 0 - A - B ; 31 if( n < cur.step ) continue ; 32 if( A == a && B == b && C == c ){ 33 cout << cur.step << endl; 34 return ; 35 } 36 for( int i = 0 ; i < 18 ; i++ ){ 37 int tx = A + p[i] ; 38 int ty = B + q[i] ; 39 if( -600 <= tx && tx <= 600 && -600 <= ty && ty <= 600 ){ 40 if( !vis[tx+M][ty+M] ){ 41 Q.push( Node{tx , ty , cur.step+1 } ); 42 vis[tx+M][ty+M] = 1 ; 43 } 44 } 45 } 46 } 47 cout << -1 << endl; 48 return ; 49 } 50 int main() 51 { 52 ios_base :: sync_with_stdio(false); 53 cin.tie(NULL) , cout.tie(NULL); 54 cin >> n >> a >> b >> c ; 55 if( a == 0 && b == 0 && c == 0 ){ 56 if( n >= 2 ) cout << 2 << endl; 57 else cout << -1 << endl ; 58 }else{ 59 BFS(); 60 } 61 return 0; 62 }