本文主要是介绍NYOJ21 【三个水杯】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
描述- 输入
- 第一行一个整数N(0<N<50)表示N组测试数据
接下来每组测试数据有两行,第一行给出三个整数V1 V2 V3 (V1>V2>V3 V1<100 V3>0)表示三个水杯的体积。
第二行给出三个整数E1 E2 E3 (体积小于等于相应水杯体积)表示我们需要的最终状态 输出 - 每行输出相应测试数据最少的倒水次数。如果达不到目标状态输出-1 样例输入
-
2 6 3 1 4 1 1 9 3 2 7 1 1
样例输出 -
3 -1
//NYOJ21_BFS
#include <stdio.h>
#include <string.h>
#include <queue>
using std::queue;struct Node{int v[3];int steps;
} init, targ;
bool vis[100][100][100];bool del(Node &cup, int start, int end){if(cup.v[start] && cup.v[end] != init.v[end]){ //能倒水int sum = cup.v[start] + cup.v[end];if(sum >= init.v[end]) cup.v[end] = init.v[end];else cup.v[end] = sum;cup.v[start] = sum - cup.v[end];if(!vis[cup.v[0]][cup.v[1]][cup.v[2]])return vis[cup.v[0]][cup.v[1]][cup.v[2]] = true; }return false;
}int BFS(){Node cup = {init.v[0], 0, 0, 0}, temp;queue<Node> Q;memset(vis, 0, sizeof(vis));vis[init.v[0]][0][0] = true;Q.push(cup);while(!Q.empty()){temp = cup = Q.front();if(temp.v[0] == targ.v[0] && temp.v[1] == targ.v[1]&& temp.v[2] == targ.v[2]) return temp.steps;Q.pop();for(int i = 0; i < 3; ++i){ for(int j = 0; j < 3; ++j){temp = cup;if(i != j && del(temp, i, j)){ ++temp.steps; Q.push(temp); }}}}return -1;
}int main(){int t;scanf("%d", &t);while(t--){scanf("%d%d%d", init.v, init.v + 1, init.v + 2);scanf("%d%d%d", targ.v, targ.v + 1, targ.v + 2);printf("%d\n", BFS());}return 0;
}
这篇关于NYOJ21 【三个水杯】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!