NYOJ(21)，BFS，三个水杯

题目链接：http://acm.nyist.net/JudgeOnline/problem.php?pid=21

BFS判环，vis标记状态即可。

#include <stdio.h> #include <queue> #include <string.h>using namespace std;bool vis[100][100][100];struct Cup {int v[3];int step; };int s[3],t[3];int bfs() {memset(vis,false,sizeof(vis));Cup start;start.step = 0;start.v[0] = s[0];start.v[1] = 0;start.v[2] = 0;vis[s[0]][0][0] = true;queue<Cup> Q;Q.push(start);while(!Q.empty()){start = Q.front();Q.pop();if(start.v[0]==t[0]&&start.v[1]==t[1]&&start.v[2]==t[2])return start.step;for(int i=0; i<3; i++){for(int j=0; j<3; j++){Cup tmp = start;if(i==j||tmp.v[i]==0||tmp.v[j]==s[j])continue;if(tmp.v[i]+tmp.v[j]<=s[j]){tmp.v[j] = tmp.v[i]+tmp.v[j];tmp.v[i] = 0;}else{tmp.v[i] = tmp.v[i] - (s[j]-tmp.v[j]);tmp.v[j] = s[j];}tmp.step++;if(!vis[tmp.v[0]][tmp.v[1]][tmp.v[2]]){Q.push(tmp);vis[tmp.v[0]][tmp.v[1]][tmp.v[2]] = true;}}}}return -1; }int main() {int cases;scanf("%d",&cases);while(cases--){for(int i=0; i<3; i++)scanf("%d",&s[i]);for(int i=0; i<3; i++)scanf("%d",&t[i]);printf("%d\n",bfs());}return 0; }

 

转载于:https://www.cnblogs.com/TreeDream/p/5742186.html

总结

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

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