求助POJ3414
  • 板块灌水区
  • 楼主__2304__
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/6/3 22:21
  • 上次更新2024/6/4 22:22:12
查看原帖
求助POJ3414
719611
__2304__楼主2024/6/3 22:21

为什么一直RE,有人能出一个hack数据吗

#include<iostream>
#include<queue>
#include<stack>
#include<cstring>
using namespace std;
int A,B,C,vis[101][101];
struct pot{
	int a,b,t,opt,prev;
};
pot q[5000005];
stack<int> o;
int f=1,e=1,flag=0;
void bfs()
{
	while(f<=e){
		//cout<<q[f].a<<" "<<q[f].b<<" "<<q[f].t<<" "<<q[f].opt<<" "<<q[f].prev<<endl;
		if(q[f].a==C||q[f].b==C){
			cout<<q[f].t<<endl;
			flag=1;
			break;
		}
		if(!vis[q[f].a][0]){
			pot p;
			p.a=q[f].a,p.b=0,p.t=q[f].t+1,p.opt=1,p.prev=f;//opt 1:drop 2
			vis[p.a][p.b]=1;
			e++;q[e]=p;
		}
		if(!vis[0][q[f].b]){
			pot p;
			p.a=0,p.b=q[f].b,p.t=q[f].t+1,p.opt=2,p.prev=f;//opt 2:drop 1
			vis[p.a][p.b]=1;
			e++;q[e]=p;
		}
		if(!vis[q[f].a][B]){
			pot p;
			p.a=q[f].a,p.b=B,p.t=q[f].t+1,p.opt=3,p.prev=f;//opt 3:fill 2
			vis[p.a][p.b]=1;
			e++;q[e]=p;
		}
		if(!vis[A][q[f].b]){
			pot p;
			p.a=A,p.b=q[f].b,p.t=q[f].t+1,p.opt=4,p.prev=f;//opt 4:fill 1;
			vis[p.a][p.b]=1;
			e++;q[e]=p;
		}
		if(!vis[min(q[f].a+q[f].b,A)][max(0,q[f].b-A+q[f].a)]){
			pot p;
			p.a=min(q[f].a+q[f].b,A),p.b=max(0,q[f].b-A+q[f].a),p.t=q[f].t+1,p.opt=5,p.prev=f;//opt 5:pour 2 to 1
			vis[p.a][p.b]=1;
			e++;q[e]=p;
		}
		if(!vis[max(0,q[f].a-B+q[f].b)][min(q[f].b+q[f].a,B)]){
			pot p;
			p.a=max(0,q[f].a-B+q[f].b),p.b=min(q[f].b+q[f].a,B),p.t=q[f].t+1,p.opt=6,p.prev=f;//opt 6:pour 1 to 2
			vis[p.a][p.b]=1;
			e++;q[e]=p;
		}
		f++;
	}
	if(!flag) cout<<"impossible";
}
int main()
{
	cin>>A>>B>>C;
	pot p;
	p.a=0,p.b=0,p.t=0;
	q[f]=p;
	bfs();
	if(!flag) return 0;
	int i=e-1;
	while(q[i].prev){
		o.push(q[i].opt);
		i=q[i].prev;
	}
	while(!o.empty()){
		if(o.top()==1) cout<<"DROP(2)"<<endl;
		else if(o.top()==2) cout<<"DROP(1)"<<endl;
		else if(o.top()==3) cout<<"FILL(2)"<<endl;
		else if(o.top()==4) cout<<"FILL(1)"<<endl;
		else if(o.top()==5) cout<<"POUR(2,1)"<<endl;
		else if(o.top()==6) cout<<"POUR(1,2)"<<endl;
		o.pop();
	}
	return 0;
}
2024/6/3 22:21
加载中...