NYOJ--21--bfs--三个水杯

/* 输入 第一行一个整数N(0<N<50)表示N组测试数据 接下来每组测试数据有两行，第一行给出三个整数V1 V2 V3 (V1>V2>V3 V1<100 V3>0)表示三个水杯的体积。 第二行给出三个整数E1 E2 E3 （体积小于等于相应水杯体积）表示我们需要的最终状态 输出 每行输出相应测试数据最少的倒水次数。如果达不到目标状态输出-1 */ /*Name: NYOJ--21--三个水杯Author: shen_渊 Date: 17/04/17 10:27Description: */ #include<iostream> #include<queue> #include<cstring> using namespace std; struct wat{int v[3],s[3],step;wat():step(0){}; }; int bfs(); int vis[101][101][101],ans; wat s,d; int main(){ // freopen("in.txt","r",stdin);ios::sync_with_stdio(false);int n;cin>>n;while(n--){memset(vis,0,sizeof(vis));ans = 0x7fffffff;cin>>s.v[0]>>s.v[1]>>s.v[2];cin>>d.v[0]>>d.v[1]>>d.v[2];s.s[0] = s.v[0];s.s[1] = 0;s.s[2] = 0;if(s.v[0] < d.v[0]+d.v[1]+d.v[2]){cout<<"-1"<<endl;continue;}if(s.v[0] == d.v[0] && d.v[1] == 0&&d.v[2]==0){cout<<"0"<<endl;continue;}cout<<bfs()<<endl;}return 0; } int bfs(){queue<wat> q;q.push(s);vis[s.s[0]][s.s[1]][s.s[2]] = 1;int i = 0;while(!q.empty()){if(i++>1000000)break;wat temp = q.front();q.pop();if(temp.s[0]==d.v[0] && temp.s[1] == d.v[1] && temp.s[2] == d.v[2])return temp.step;for(int i=0; i<3; ++i){for(int j=0; j<3; ++j){if(i == j)continue;//剪枝 wat a = temp;int minwater = a.v[j] - a.s[j];// 倒满情况下需要的水 if(a.s[i]<minwater){//不够就倒完 minwater = a.s[i]; }a.s[i] -= minwater;a.s[j] += minwater;a.step++;if(!vis[a.s[0]][a.s[1]][a.s[2]]){ // cout<<"当前水的状态："<<i<<" :"<<a.s[0]<<" "<<a.s[1]<<" "<<a.s[2]<<endl; q.push(a);vis[a.s[0]][a.s[1]][a.s[2]] = 1;//a.s[0]写的s.s[0]死循环了，被自己搞死了 } }}}return -1; }

 

转载于:https://www.cnblogs.com/evidd/p/7251876.html

总结

以上是生活随笔为你收集整理的NYOJ--21--bfs--三个水杯的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。