nyoj 21 three water cups (simulated bfs)

Three water glasses

Time limit: 1000 ms | memory limit: 65535 KB
Difficulty: 4
describe Give three glasses of different sizes, and only the largest one is full, the other two are empty. The three water cups pour water into each other, and the water cup has no mark, so it can only be calculated according to the given volume of the water cup. Now you are asked to write a program that outputs the minimum number of times the initial state reaches the target state.
input An integer N (0 < N < 50) in the first row indicates the test data of group N
Next, each group of test data has two lines. The first line gives three integers V1 V2 V3 (V1 > V2 > V3 V1 < 100 V3 > 0), indicating the volume of three water cups.
The second line gives three integers E1 E2 E3 (the volume is less than or equal to the corresponding water cup volume) to represent the final state we need output Output the minimum number of pour times of corresponding test data for each line. If the target state output-1 is not reached sample input
2
6 3 1
4 1 1
9 3 2
7 1 1
sample output
3
-1

Idea: there are six states (three water cups pour water into each other) in each cycle. Each time, select the smaller one from the maximum capacity a[i] that can be reached by the water pouring cup and the maximum capacity v[j]-a[j] that can be filled by the water pouring cup, and then check whether the state d[a[0]][a[1]][a[2]] has been accessed. If not, join the queue, and no matter if it has been visited.

AC Code:

#include<cstdio>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 100 + 2;
int d[maxn][maxn][maxn];
struct node{
	int cnt; //So far, how many times to pour water 
	int a,b,c;  //Current capacity of three cups 
	node(int a,int b,int c,int cnt):a(a),b(b),c(c),cnt(cnt){}
	node(){}
	bool operator < (const node& nd)const {   //The first out queue with the smaller cnt value 
	     return this->cnt > nd.cnt;
	}
} ns,ne;

int v[3];//Cup capacity 

void bfs(){
	memset(d,0,sizeof(d));
	d[ns.a][ns.b][ns.c] = 1;  //This state has been accessed 
	priority_queue<node> q;
	q.push(ns);
	while(!q.empty()){
		node u = q.top(); q.pop();
		if(u.a == ne.a && u.b == ne.b && u.c == ne.c){
			printf("%d\n",u.cnt);
			return ;
		}

		for(int i = 0; i < 3; i++){	//A cup for pouring water out 
			for(int j = 0; j < 3; j++){  //A cup into which water is poured 
				int a[3]={u.a,u.b,u.c};	
				if(i != j){
				   int Min = min(a[i],v[j]-a[j]);  //Choose the smaller one from the cup with the capacity of a[i] and the cup with the capacity of v[j]-a[j] 
				   a[i] -= Min;
				   a[j] += Min;					
				if(!d[a[0]][a[1]][a[2]]){
					d[a[0]][a[1]][a[2]] = 1;
					q.push(node(a[0],a[1],a[2],u.cnt + 1));
				}
			  }
			}
		} 
	}
	
	printf("-1\n");
}

int main(){
	int n;
	scanf("%d",&n);
	while(n--){
		scanf("%d%d%d",&v[0],&v[1],&v[2]);  //Cup capacity 
		scanf("%d%d%d",&ne.a,&ne.b,&ne.c);  //Target status 
		ns.a = v[0] ,ns.b = 0, ns.c = 0, ns.cnt = 0;
		if((ne.a + ne.b + ne.c) > v[0]){
			printf("-1\n"); continue;
		}
		bfs();
	} 
	return 0;
}




Tags: less

Posted on Sun, 03 May 2020 06:15:42 -0700 by webbyboy