2 条题解
-
018017894 LV 9 MOD @ 2018-04-11 16:11:29
抓住那头牛(不使用构造函数)
//抓住那头牛(POJ3278) #include <iostream> #include <cstring> #include <cstdio> #include <algorithm> #include <cmath> #include <cstdlib> #include <queue> using namespace std; const int MAXN = 100000; struct Step{ int x; //位置 int steps; //表示到达x所需步数 }; queue<Step> q; //队列 int visited[MAXN + 5] = {}; //判重标记 , visited[i]=ture 表示i已扩展过 int main(){ int N,K; scanf("%d%d", &N, &K); Step s,ss; s.x=N; s.steps=0; memset(visited, 0, sizeof(visited));//初始化数组visited[]为零 q.push(s);//效果一样的 visited[N] = 1; while(!q.empty()){ s = q.front(); //定义后:s 即 Step 结构体 if(s.x == K) {//找到目标 printf("%d\n", s.steps); return 0; } else { if(s.x - 1 >= 0 && !visited[s.x - 1]) //如果没有扩展过 { ss.x=s.x-1; ss.steps=s.steps+1;//扩展,步数++ q.push(ss); visited[s.x - 1] = 1; } if(s.x + 1 <= MAXN && !visited[s.x + 1]) { ss.x=s.x+1; ss.steps=s.steps+1;//扩展,步数++ q.push(ss); visited[s.x + 1] = 1; } if(s.x * 2 <= MAXN && !visited[s.x *2]) { ss.x=s.x*2;ss.steps=s.steps+1;//扩展,步数++ q.push(ss); visited[s.x * 2] = 1; } q.pop(); } } return 0; }
-
02018-04-11 16:11:00@
抓住那头牛(使用构造函数)
//抓住那头牛(POJ3278) #include <iostream> #include <cstring> #include <cstdio> #include <algorithm> #include <cmath> #include <cstdlib> #include <queue> using namespace std; const int MAXN = 100000; struct Step{ int x; //位置 int steps; //表示到达x所需步数 Step(int xx, int s):x(xx), steps(s){} //定义后:xx 即 Step 中 x, s 即 Step 中 steps }; queue<Step> q; //队列 int visited[MAXN + 5] = {}; //判重标记 , visited[i]=ture 表示i已扩展过 int main(){ int N,K; scanf("%d%d", &N, &K); //ss.x=N;ss.steps=0; memset(visited, 0, sizeof(visited));//初始化数组visited[]为零 q.push(Step(N, 0));//q.push(ss);//效果一样的 visited[N] = 1; while(!q.empty()){ Step s = q.front(); //定义后:s 即 Step 结构体 if(s.x == K) {//找到目标 printf("%d\n", s.steps); return 0; } else { if(s.x - 1 >= 0 && !visited[s.x - 1]) //如果没有扩展过 { //ss.x=s.x-1;ss.steps=steps+1; q.push(Step(s.x-1, s.steps + 1)); //扩展,步数++ //不用构造函数 用结构体直接赋值也可 q.push(ss); visited[s.x - 1] = 1; } if(s.x + 1 <= MAXN && !visited[s.x + 1]) { q.push(Step(s.x + 1, s.steps + 1)); visited[s.x + 1] = 1; } if(s.x * 2 <= MAXN && !visited[s.x *2]) { q.push(Step(s.x * 2, s.steps + 1)); visited[s.x * 2] = 1; } q.pop(); } } return 0; }
- 1