首页 > 代码库 > POJ3185(简单BFS，主要做测试使用)
POJ3185(简单BFS，主要做测试使用)
没事做水了一道POJ的简单BFS的题目
这道题的数据范围是20,所以状态总数就是（1<<20）
第一次提交使用STL的queue，并且是在队首判断是否达到终点，达到终点就退出，超时：（其实这里我是很不明白的，，TM状态总数就只有1e6怎么也不应该超时的，，，，只能说STL的queue的常数实在是太大，完全没法弄。。。）
1 #include <map> 2 #include <set> 3 #include <stack> 4 #include <queue> 5 #include <cmath> 6 #include <ctime> 7 #include <vector> 8 #include <cstdio> 9 #include <cctype>10 #include <cstring>11 #include <string.h>12 #include <cstdlib>13 #include <iostream>14 #include <algorithm>15 using namespace std;16 #define INF 1e917 #define inf (-((LL)1<<40))18 #define lson k<<1, L, mid19 #define rson k<<1|1, mid+1, R20 #define mem0(a) memset(a,0,sizeof(a))21 #define mem1(a) memset(a,-1,sizeof(a))22 #define mem(a, b) memset(a, b, sizeof(a))23 #define FOPENIN(IN) freopen(IN, "r", stdin)24 #define FOPENOUT(OUT) freopen(OUT, "w", stdout)25 template<class T> T CMP_MIN(T a, T b) { return a < b; }26 template<class T> T CMP_MAX(T a, T b) { return a > b; }27 template<class T> T MAX(T a, T b) { return a > b ? a : b; }28 template<class T> T MIN(T a, T b) { return a < b ? a : b; }29 template<class T> T GCD(T a, T b) { return b ? GCD(b, a%b) : a; }30 template<class T> T LCM(T a, T b) { return a / GCD(a,b) * b; }31 template<class T> void SWAP(T& a, T& b) { T x = a; a = b; b = x; }32 33 //typedef __int64 LL;34 typedef long long LL;35 const int MAXN = 200010;36 const int MAXM = 100005;37 const double eps = 1e-10;38 //const LL MOD = 1000000007;39 40 int step[1<<21];41 bool vis[1<<21];42 43 int BFS(int s)44 {45 vis[s] = 1;46 queue<int>q;47 q.push(s);48 step[s] = 0;49 while(!q.empty())50 {51 int u = q.front(); q.pop();52 if(u == 0) return step[u];53 for(int i=1;i<19;i++)54 {55 int r = u;56 r ^= (1<<i-1) | (1<<i) | (1<<i+1);57 if(!vis[r])58 {59 vis[r] = 1;60 step[r] = step[u] + 1;61 q.push(r);62 }63 }64 int r = u ^ (1<<0) ^ (1<<1);65 if(!vis[r]) { vis[r] = 1; step[r] = step[u] + 1; q.push(r); }66 r = u ^ (1<<18) ^ (1<<19);67 if(!vis[r]) { vis[r] = 1; step[r] = step[u] + 1; q.push(r); }68 }69 return -1;70 }71 72 int main()73 {74 //FOPENIN("in.txt");75 int st = 0, x;76 for(int i=0;i<20;i++)77 {78 scanf("%d", &x);79 st |= (x<<i);80 }81 printf("%d\n", BFS(st));82 return 0;83 }
TLE后马上把判断放到队尾（就是说在一个状态进队列前先判断是不是终点状态，是的话就退出），跑了875ms，勉强过了，，（这里我就是乱改的了，代码没任何观赏性）
1 #include <map> 2 #include <set> 3 #include <stack> 4 #include <queue> 5 #include <cmath> 6 #include <ctime> 7 #include <vector> 8 #include <cstdio> 9 #include <cctype>10 #include <cstring>11 #include <string.h>12 #include <cstdlib>13 #include <iostream>14 #include <algorithm>15 using namespace std;16 #define INF 1e917 #define inf (-((LL)1<<40))18 #define lson k<<1, L, mid19 #define rson k<<1|1, mid+1, R20 #define mem0(a) memset(a,0,sizeof(a))21 #define mem1(a) memset(a,-1,sizeof(a))22 #define mem(a, b) memset(a, b, sizeof(a))23 #define FOPENIN(IN) freopen(IN, "r", stdin)24 #define FOPENOUT(OUT) freopen(OUT, "w", stdout)25 template<class T> T CMP_MIN(T a, T b) { return a < b; }26 template<class T> T CMP_MAX(T a, T b) { return a > b; }27 template<class T> T MAX(T a, T b) { return a > b ? a : b; }28 template<class T> T MIN(T a, T b) { return a < b ? a : b; }29 template<class T> T GCD(T a, T b) { return b ? GCD(b, a%b) : a; }30 template<class T> T LCM(T a, T b) { return a / GCD(a,b) * b; }31 template<class T> void SWAP(T& a, T& b) { T x = a; a = b; b = x; }32 33 //typedef __int64 LL;34 typedef long long LL;35 const int MAXN = 200010;36 const int MAXM = 100005;37 const double eps = 1e-10;38 //const LL MOD = 1000000007;39 40 int step[1<<21];41 bool vis[1<<21];42 43 int BFS(int s)44 {45 vis[s] = 1;46 queue<int>q;47 q.push(s);48 step[s] = 0;49 while(!q.empty())50 {51 int u = q.front(); q.pop();52 if(u == 0) return step[u];53 for(int i=1;i<19;i++)54 {55 int r = u;56 r ^= (1<<i-1) | (1<<i) | (1<<i+1);57 if(!vis[r])58 {59 vis[r] = 1;60 step[r] = step[u] + 1;61 if(r==0) return step[r];62 q.push(r);63 }64 }65 int r = u ^ (1<<0) ^ (1<<1);66 if(!vis[r]) { vis[r] = 1; step[r] = step[u] + 1; q.push(r); if(r==0) return step[r];}67 r = u ^ (1<<18) ^ (1<<19);68 if(!vis[r]) { vis[r] = 1; step[r] = step[u] + 1; q.push(r); if(r==0) return step[r];}69 }70 return -1;71 }72 73 int main()74 {75 //FOPENIN("in.txt");76 int st = 0, x;77 for(int i=0;i<20;i++)78 {79 scanf("%d", &x);80 st |= (x<<i);81 }82 printf("%d\n", BFS(st));83 return 0;84 }
然后突然想起之前写过一个静态队列的模板，是用循环队列写的，想着正好去测试下，就改了队列的定义，其他使用完全一致，没任何修改，结果跑了250ms快了好多了啊有木有。。
1 #include <map> 2 #include <set> 3 #include <stack> 4 #include <queue> 5 #include <cmath> 6 #include <ctime> 7 #include <vector> 8 #include <cstdio> 9 #include <cctype> 10 #include <cstring> 11 #include <string.h> 12 #include <cstdlib> 13 #include <iostream> 14 #include <algorithm> 15 using namespace std; 16 #define INF 1e9 17 #define inf (-((LL)1<<40)) 18 #define lson k<<1, L, mid 19 #define rson k<<1|1, mid+1, R 20 #define mem0(a) memset(a,0,sizeof(a)) 21 #define mem1(a) memset(a,-1,sizeof(a)) 22 #define mem(a, b) memset(a, b, sizeof(a)) 23 #define FOPENIN(IN) freopen(IN, "r", stdin) 24 #define FOPENOUT(OUT) freopen(OUT, "w", stdout) 25 template<class T> T CMP_MIN(T a, T b) { return a < b; } 26 template<class T> T CMP_MAX(T a, T b) { return a > b; } 27 template<class T> T MAX(T a, T b) { return a > b ? a : b; } 28 template<class T> T MIN(T a, T b) { return a < b ? a : b; } 29 template<class T> T GCD(T a, T b) { return b ? GCD(b, a%b) : a; } 30 template<class T> T LCM(T a, T b) { return a / GCD(a,b) * b; } 31 template<class T> void SWAP(T& a, T& b) { T x = a; a = b; b = x; } 32 33 //typedef __int64 LL; 34 typedef long long LL; 35 const int MAXN = 200010; 36 const int MAXM = 100005; 37 const double eps = 1e-10; 38 //const LL MOD = 1000000007; 39 40 41 //MyQueue<Type>q; 42 //定义了一个固定长度的队列， 不能动态增长 43 //构造时不传参数，队列大小为1e5，传入参数时为自定义大小 44 //如果队列不为空，front返回队首元素， 45 //如果队列为空，pop无效，front返回NULL 46 //clear将队列清空, 供多次使用 47 //如果push时产生冲突，即队列已满， 将加入失败 48 template <class T> 49 class MyQueue 50 { 51 private: 52 T* que; 53 int si, fr, re; 54 void setValue(int _size) { 55 fr = 0; re = 0; 56 si = _size; 57 que = (T*)malloc(si * sizeof(T)); 58 } 59 public: 60 MyQueue() { 61 this->setValue(100005); 62 } 63 MyQueue(int _size) { 64 this->setValue(_size); 65 } 66 T front() { 67 if(fr != re) 68 return que[fr]; 69 return NULL; 70 } 71 void pop() { 72 if(fr != re) 73 fr = (fr + 1) % si; 74 } 75 void push(T e) { 76 if((re + 1) % si == fr) return ; 77 que[re] = e; 78 re = (re + 1) % si; 79 } 80 bool empty() { 81 if(fr == re) return 1; 82 return 0; 83 } 84 void clear() { 85 fr = 0; 86 re = 0; 87 } 88 }; 89 90 int step[1<<21]; 91 bool vis[1<<21]; 92 93 int BFS(int s) 94 { 95 vis[s] = 1; 96 MyQueue<int>q(1<<21);//定义队列的大小为(1<<21),其他无任何修改 97 q.push(s); 98 step[s] = 0; 99 while(!q.empty())100 {101 int u = q.front(); q.pop();102 if(u == 0) return step[u];103 for(int i=1;i<19;i++)104 {105 int r = u;106 r ^= (1<<i-1) | (1<<i) | (1<<i+1);107 if(!vis[r])108 {109 vis[r] = 1;110 step[r] = step[u] + 1;111 q.push(r);112 }113 }114 int r = u ^ (1<<0) ^ (1<<1);115 if(!vis[r]) { vis[r] = 1; step[r] = step[u] + 1; q.push(r); }116 r = u ^ (1<<18) ^ (1<<19);117 if(!vis[r]) { vis[r] = 1; step[r] = step[u] + 1; q.push(r); }118 }119 return -1;120 }121 122 int main()123 {124 //FOPENIN("in.txt");125 int st = 0, x;126 for(int i=0;i<20;i++)127 {128 scanf("%d", &x);129 st |= (x<<i);130 }131 printf("%d\n", BFS(st));132 return 0;133 }
最后试着把终点判断放在队头，依然360ms就跑出来了啊，，，我就哭了。。。
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。