yzoi1777倒水问题
  • 板块学术版
  • 楼主Chtholly__Nota
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/7/20 16:23
  • 上次更新2024/7/20 17:25:41
查看原帖
yzoi1777倒水问题
847559
Chtholly__Nota楼主2024/7/20 16:23

这是我的代码,问思路有问题吗?

#include <bits/stdc++.h>
using namespace std;

struct node{
	int v[3];
	int pre,step,its;
};
int x,y,z,n,vmax[3],vis[1000][1000][1000];
queue<node> q;

node jl[1000000];

vector<node> a;

node p(node temp,int i,int j){
	int sum=temp.v[i]+temp.v[j];
	if(sum>vmax[j]){
		temp.v[i]-=vmax[j]-temp.v[j];
		temp.v[j]=vmax[j];
	}
	else{
		temp.v[i]=0;
		temp.v[j]+=temp.v[i];
	}
	return temp;
}


int main() {
	cin>>vmax[0]>>vmax[1]>>vmax[2]>>n;
	node t;
	t.v[0]=vmax[0];
	t.v[1]=0;
	t.v[2]=0;
	t.pre=0;
	t.step=0;
	t.its=0;
	jl[0]=t;
	q.push(t);
	int js=0;
	while(!q.empty()){
		node ts=q.front();
		vis[ts.v[0]][ts.v[1]][ts.v[2]]=1;
		for(int i=0;i<3;i++){
			for(int j=0;j<3;j++){
				if(i!=j){
					js++;
					node ts1=p(ts,i,j);
					if(!vis[ts1.v[0]][ts1.v[1]][ts1.v[2]]){
						jl[i]=ts1;
						ts1.its=js;
						ts1.step=ts.step+1;
						ts1.pre=ts.its;
						q.push(ts1);
					}
					for(int k=0;k<3;k++){
						if(ts1.v[k]==n){
							node sy=ts1;
							if(ts1.step==1) cout<<"1 step"<<endl;
							else cout<<ts1.step<<" steps"<<endl;
							while(sy.pre!=0){
								a.push_back(sy);
								sy=jl[sy.pre];
							}
							int jj=0;
							for(int ii=a.size()-1;ii>=0;ii--,jj++){
								cout<<"step"<<jj<<':'<<" "<<a[i].v[0]<<" "<<a[i].v[1]<<" "<<a[i].v[2]<<endl;
							}
							return 0;
						}
					}
				}
				
			}
		}
		q.pop();
	}
  	return 0;
}


2024/7/20 16:23
加载中...