poj 3278 Catch That Cow 广度优先搜索 + 回溯 队列 剪枝

#include<iostream> #include<stdio.h> #include<vector> using namespace std; int num; int sign=100000;//当kk>k的时候剪枝 int n,k; bool c[100001];//记录是否已经使用过 vector<int> test[2];//队列交替 vector<int>::iterator t; int DFS(); int main() { scanf("%d%d",&n,&k); if(n>=k){printf("%d",n-k);return 0;} num=0; test[num].push_back(n); c[n]=true; DFS(); printf("%d",num); return 0; } int DFS() { int a=num%2; num++; if(sign<=num){num=sign;return 0;} int b=num%2; int kk; while(!test[a].empty()) { kk=test[a].front(); t=test[a].begin(); test[a].erase(t); if(k==kk-1||k==kk+1||k==kk*2){ return 0;} else if(kk>=k) { if(kk-k+num<sign)sign=kk-k+num; } else { if(kk-1>=0&&kk-1<=100000&&!c[kk-1])test[b].push_back(kk-1),c[kk-1]=true; if(kk+1>=0&&kk+1<=100000&&!c[kk+1])test[b].push_back(kk+1),c[kk+1]=true; if(kk*2>=0&&kk*2<=100000&&!c[kk*2])test[b].push_back(kk*2),c[kk*2]=true; } } DFS(); return 0; }

本程序优于第一个程序，0ms通过。第一个程序在队列删除元素上浪费大量时间。 #include<iostream> #include<stdio.h> #include<vector> using namespace std; int num; int sign=100000; int x,y; int n,k; bool c[100001]; vector<int> test[2]; int DFS(); int main() { scanf("%d%d",&n,&k); if(n>=k){printf("%d",n-k);return 0;} num=0; test[num].push_back(n); c[n]=true; DFS(); printf("%d",num); return 0; } int DFS() { int a=num%2; num++; if(sign<=num){num=sign;return 0;} int b=num%2; int kk; int i; if(a==0)i=x; else i=y; while(i<test[a].size()) { kk=test[a][i]; i++; if(k==kk-1||k==kk+1||k==kk*2){ return 0;} else if(kk>=k) { if(kk-k+num<sign)sign=kk-k+num; } else { if(kk-1>=0&&!c[kk-1])test[b].push_back(kk-1),c[kk-1]=true; if(kk+1<=100000&&!c[kk+1])test[b].push_back(kk+1),c[kk+1]=true; if(kk*2<=100000&&!c[kk*2])test[b].push_back(kk*2),c[kk*2]=true; } } if(a==0)x=i; else y=i; DFS(); return 0; }

//本程序 0ms通过 队列不删除 删除费时 没有递归 不用标记属于第几层 #include<iostream> #include<stdio.h> #include<vector> using namespace std; int num; int sign=100000; int n,k; bool c[100001]; int f[100001]; vector<int> test; int DFS(); int main() { scanf("%d%d",&n,&k); if(n>=k){printf("%d",n-k);return 0;} num=0; test.push_back(n);f[n]=0; c[n]=true; DFS(); printf("%d",f[k]); return 0; } int DFS() { int kk;int i=0; while(i<test.size()) { kk=test[i]; i++; if(kk-1>=0&&!c[kk-1])test.push_back(kk-1),c[kk-1]=true,f[kk-1]=f[kk]+1; if(kk+1<=100000&&!c[kk+1])test.push_back(kk+1),c[kk+1]=true,f[kk+1]=f[kk]+1; if(kk*2<=100000&&!c[kk*2])test.push_back(kk*2),c[kk*2]=true,f[kk*2]=f[kk]+1; } return 0; }

本人修改后的最有程序。0ms536k省时间省内存 两队列交替使用，随时清空从新使用，不记录已求出的最短时间（没有f数组）. #include<iostream> #include<stdio.h> #include<vector> using namespace std; int num; int sign=100000; int x,y; int n,k; bool c[100001]; vector<int> test[2]; int DFS(); int main() { scanf("%d%d",&n,&k); if(n>=k){printf("%d",n-k);return 0;} num=0; test[num].push_back(n); c[n]=true; DFS(); printf("%d",num); return 0; } int DFS() { int a=num%2; num++; if(sign<=num){num=sign;return 0;} int b=num%2; int kk; int i=0; while(i<test[a].size()) { kk=test[a][i]; i++; if(k==kk-1||k==kk+1||k==kk*2){ return 0;} else if(kk>=k) { if(kk-k+num<sign)sign=kk-k+num; } else { if(kk-1>=0&&!c[kk-1])test[b].push_back(kk-1),c[kk-1]=true; if(kk+1<=100000&&!c[kk+1])test[b].push_back(kk+1),c[kk+1]=true; if(kk*2<=100000&&!c[kk*2])test[b].push_back(kk*2),c[kk*2]=true; } } test[a].clear(); DFS(); return 0; }

最后

以上就是辛勤钢笔为你收集整理的poj 3278 Catch That Cow 广度优先搜索 + 回溯 队列 剪枝的全部内容，希望文章能够帮你解决poj 3278 Catch That Cow 广度优先搜索 + 回溯 队列 剪枝所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。