題目鏈接：點擊查看

題目大意：給出斗地主的規則，以及最終分數，求出最少需要進行幾局游戲

題目分析：bfs爆搜即可，因為數據范圍比較小，我一開始沒多想，直接18種情況全部打上去，交了一發T掉了。。bfs被卡T？于是就剪枝，剪了半天還是T，最后拿出秘密武器，用無序map+600進制維護了vis數組，就A了，因為不想出現負數，而且a,b,c的數據范圍都比較小，直接都加上300變成正數然后按照600進制處理即可，沒什么細節。。裸題一個。

不過雖然過了，但還是跑了800多ms，看到有的人交了30多ms的就有點在意，去網上搜了搜，發現，原來只需要維護一個二維數組即可，因為題目中保證了a+b+c恒等于0，所以枚舉a和b的情況，c的情況就已經知道了，所以只需要對a和b進行操作就好了，懶得再寫代碼了，下次看到這種題目應該會留個印象了，掛代碼吧，主要是學到了一波如何用二維思想實現三維的題目吧（雖然我還是用三維莽過去的。。）

#include<iostream> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<unordered_map> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e6+100;int n,a,b,c;const int bb[][3]= { //win 2,-1,-1,//A 4,-2,-2, 6,-3,-3, -1,2,-1,//B -2,4,-2, -3,6,-3, -1,-1,2,//C -2,-2,4, -3,-3,6, //lose -2,1,1,//A -4,2,2, -6,3,3, 1,-2,1,//B 2,-4,2, 3,-6,3, 1,1,-2,//C 2,2,-4, 3,3,-6 };unordered_map<int,int>vis;struct Node {int step;int a,b,c; };int getnum(int a,int b,int c) {return a*600*600+b*600+c; }int bfs() {a+=300;b+=300;c+=300;queue<Node>q;vis.clear();Node temp;temp.a=300;temp.b=300;temp.c=300;temp.step=0;q.push(temp);while(!q.empty()){Node cur=q.front();q.pop(); // cout<<cur.step<<' '<<cur.a<<' '<<cur.b<<' '<<cur.c<<endl; // cout<<cur.step<<endl;if(cur.step>n)break;for(int i=0;i<18;i++){Node next;next.a=cur.a+bb[i][0];next.b=cur.b+bb[i][1];next.c=cur.c+bb[i][2];if(vis[getnum(next.a,next.b,next.c)])continue;if(next.a>600||next.b>600||next.c>600)continue;if(next.a<0||next.b<0||next.c<0)continue;vis[getnum(next.a,next.b,next.c)]=1;next.step=cur.step+1;q.push(next);if(next.a==a&&next.b==b&&next.c==c)return next.step;}}return -1; }int main() {scanf("%d%d%d%d",&n,&a,&b,&c);printf("%d\n",bfs());return 0; }

?

總結

以上是生活随笔為你收集整理的中石油训练赛 - 斗地主(bfs)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。