OR95. water
描述
给定四个空杯子，容量分别为S1 S2 S3 S4，允许进行以下操作：
1. 将某个杯子接满水
2. 将某个杯子里的水全部倒掉
3. 将杯子A中的水倒进杯子B，直到A倒空或者B被倒满
问最少要多少步操作才能使得这四个杯子装的水分别为T1 T2 T3 T4
输入描述
第一行四个非负整数S1 S2 S3 S4输出描述
最少的步数，若无法完成则输出-1示例1
输入:
0 2 3 4 0 1 2 4
输出:
6
说明:
过程如下：C++ 解法, 执行用时: 220ms, 内存消耗: 16764KB, 提交时间: 2020-07-29
#include<bits/stdc++.h>
using namespace std;
bool mem[64][64][64][64] = {false};
bool equal(int s[4], int T[4]){
return (s[0]==T[0])&&(s[1]==T[1])&&(s[2]==T[2])&&(s[3]==T[3]);
}
int bfs(int S[4], int T[4]){
queue<tuple<int,int,int,int>> q;
auto x = make_tuple(0,0,0,0);
q.push(x);
mem[0][0][0][0] = true;
int step = 0, cap[4]={0};
while(!q.empty()){
int size = q.size();
while(size--){
tie(cap[0],cap[1],cap[2],cap[3]) = q.front(); q.pop();
if(equal(cap, T)){
return step;
}
for(int i=0; i<3; ++i){
switch(i){
case 0: // 将某个杯子倒满
for(int j=0, tmp=0; j<4; ++j){
tmp = cap[j];
cap[j] = S[j];
x = make_tuple(cap[0], cap[1], cap[2], cap[3]);
if(!mem[cap[0]][cap[1]][cap[2]][cap[3]]){
mem[cap[0]][cap[1]][cap[2]][cap[3]]=true;
q.push(x);
}
cap[j] = tmp;
}
break;
case 1: // 将某个杯子倒空
for(int j=0, tmp=0; j<4; ++j){
tmp = cap[j];
cap[j] = 0;
x = make_tuple(cap[0], cap[1], cap[2], cap[3]);
if(!mem[cap[0]][cap[1]][cap[2]][cap[3]]){
mem[cap[0]][cap[1]][cap[2]][cap[3]]=true;
q.push(x);
}
cap[j] = tmp;
}
break;
case 2: // 将杯子j倒向杯子z
for(int j=0; j<4; ++j){
int tmp1,tmp2,need;
for(int z=0; z<4; ++z){
if(j==z) continue;
tmp1=cap[j], tmp2=cap[z];
need = min(cap[j], S[z]-cap[z]);
cap[j] -= need;
cap[z] += need;
x = make_tuple(cap[0], cap[1], cap[2], cap[3]);
if(!mem[cap[0]][cap[1]][cap[2]][cap[3]]){
mem[cap[0]][cap[1]][cap[2]][cap[3]]=true;
q.push(x);
}
cap[j]=tmp1, cap[z]=tmp2;
}
}
}//end switch
}
}//end inner while
++step;
}//end outer while
return -1;
}
int main(){
int S[4]={0}, T[4]={0};
cin>> S[0] >> S[1] >> S[2] >> S[3];
cin>> T[0] >> T[1] >> T[2] >> T[3];
if(S[0]==0 && S[1]==0 && S[2]==0 && S[3]==0 && !equal(S,T)){
cout<< -1 << endl;
}else{
int ret = bfs(S, T);
cout<< ret << endl;
}
return 0;
}
C++ 解法, 执行用时: 224ms, 内存消耗: 16760KB, 提交时间: 2020-10-31
#include<bits/stdc++.h>
using namespace std;
bool mem[64][64][64][64] = {false};
bool equal(int s[4], int T[4]){
return (s[0]==T[0])&&(s[1]==T[1])&&(s[2]==T[2])&&(s[3]==T[3]);
}
int bfs(int S[4], int T[4]){
queue<tuple<int,int,int,int>> q;
auto x = make_tuple(0,0,0,0);
q.push(x);
mem[0][0][0][0] = true;
int step = 0, cap[4]={0};
while(!q.empty()){
int size = q.size();
while(size--){
tie(cap[0],cap[1],cap[2],cap[3]) = q.front(); q.pop();
if(equal(cap, T)){
return step;
}
for(int i=0; i<3; ++i){
switch(i){
case 0: // 将某个杯子倒满
for(int j=0, tmp=0; j<4; ++j){
tmp = cap[j];
cap[j] = S[j];
x = make_tuple(cap[0], cap[1], cap[2], cap[3]);
if(!mem[cap[0]][cap[1]][cap[2]][cap[3]]){
mem[cap[0]][cap[1]][cap[2]][cap[3]]=true;
q.push(x);
}
cap[j] = tmp;
}
break;
case 1: // 将某个杯子倒空
for(int j=0, tmp=0; j<4; ++j){
tmp = cap[j];
cap[j] = 0;
x = make_tuple(cap[0], cap[1], cap[2], cap[3]);
if(!mem[cap[0]][cap[1]][cap[2]][cap[3]]){
mem[cap[0]][cap[1]][cap[2]][cap[3]]=true;
q.push(x);
}
cap[j] = tmp;
}
break;
case 2: // 将杯子j倒向杯子z
for(int j=0; j<4; ++j){
int tmp1,tmp2,need;
for(int z=0; z<4; ++z){
if(j==z) continue;
tmp1=cap[j], tmp2=cap[z];
need = min(cap[j], S[z]-cap[z]);
cap[j] -= need;
cap[z] += need;
x = make_tuple(cap[0], cap[1], cap[2], cap[3]);
if(!mem[cap[0]][cap[1]][cap[2]][cap[3]]){
mem[cap[0]][cap[1]][cap[2]][cap[3]]=true;
q.push(x);
}
cap[j]=tmp1, cap[z]=tmp2;
}
}
}//end switch
}
}//end inner while
++step;
}//end outer while
return -1;
}
int main(){
int S[4]={0}, T[4]={0};
cin>> S[0] >> S[1] >> S[2] >> S[3];
cin>> T[0] >> T[1] >> T[2] >> T[3];
if(S[0]==0 && S[1]==0 && S[2]==0 && S[3]==0 && !equal(S,T)){
cout<< -1 << endl;
}else{
int ret = bfs(S, T);
cout<< ret << endl;
}
return 0;
}