| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
貌似运作太过庞大了。。。。怎么剪啊。。。In Reply To:为什么我的一执行大数据。超过40就会BUG Posted by:4053040 at 2010-02-25 21:36:35 #include<iostream>
#include<memory>
using namespace std;
struct Que
{
int value, pre;
};Que que[30000];
int main()
{
int temp, front, rear;
int ta, tb;
int a[40000], b[40000];
int A, B, C;
int i, gg;
int visit[400][400];
void show(int pre);
cin >> A >> B >> C;
if(A % 2 == 0 && B % 2 == 0 % C % 2 != 0) { //剪枝
cout << "impossible" << endl;
return 0;
}
/*if(C > A && C > B) {
cout << "impossible" << endl;
return 0;
} */
memset(visit, 0, sizeof(visit));
gg = 0;
front = rear = 0;
a[0] = b[0] = 0;
visit[0][0] = 1;
que[0].pre = -1;
que[rear ++].value = 0;
while(front < rear) {
temp = front ++;
if(a[temp] == C || b[temp] == C) {
gg = 1;
break;
}
for(i = 1; i <= 6; i ++) {
if(i == 1) { //1 means full a
ta = A;
tb = b[temp];
}
if(i == 2) { // 2 means full b
ta = a[temp];
tb = B;
}
if(i == 3) { // 3 means empty a
ta = 0;
tb = b[temp];
}
if(i == 4) { // 4 means empty b
ta = a[temp];
tb = 0;
}
if(i == 5) { // 5 means a fills b
if(a[temp] <= B - b[temp]) { //倒不满
tb = a[temp] + b[temp];
ta = 0;
}
else { //溢出
ta = ta - (B - tb);
tb = B;
}
}
if(i == 6) { // 6 means b fills a
if(b[temp] <= A - a[temp]) {
ta = a[temp] + b[temp];
tb = 0;
}
else {
tb = b[temp] - (A - a[temp]);
ta = A;
}
}
if(visit[ta][tb] == 0) {
visit[ta][tb] = 1;
a[rear] = ta;
b[rear] = tb;
//que[rear].sum = que[front].sum + 1;
que[rear].pre = front - 1;
que[rear ++].value = i; //储存每次结果。。用于输出
}
}
}
//cout << front - 1 << endl;
if(gg == 1) {
show(front - 1);
}
else
cout << "impossible" << endl;
return 0;
}
int sum = 0;
void show(int pre)
{
sum ++;
//cout << pre << endl;
if(pre == 0) {
cout << sum - 1 << endl;
if(que[pre].value == 1)
cout << "FILL(1)" << endl;
if(que[pre].value == 2)
cout << "FILL(2)" << endl;
if(que[pre].value == 3)
cout << "DROP(1)" << endl;
if(que[pre].value == 4)
cout << "DROP(2)" << endl;
if(que[pre].value == 5)
cout << "POUR(1,2)" << endl;
if(que[pre].value == 6)
cout << "POUR(2,1)" << endl;
return ;
}
show(que[pre].pre);
//cout << que[pre].value << " ";
if(que[pre].value == 1)
cout << "FILL(1)" << endl;
if(que[pre].value == 2)
cout << "FILL(2)" << endl;
if(que[pre].value == 3)
cout << "DROP(1)" << endl;
if(que[pre].value == 4)
cout << "DROP(2)" << endl;
if(que[pre].value == 5)
cout << "POUR(1,2)" << endl;
if(que[pre].value == 6)
cout << "POUR(2,1)" << endl;
return ;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator