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