POJ3278 爆搜,不要像我一样作死就好

Posted by Cww97 on 2016-02-18

版权声明:本文为博主原创文章,未经博主允许不得转载。原文所在http://blog.csdn.net/cww97 https://blog.csdn.net/cww97/article/details/50685839
题目在这

数轴上两个点,n和k,从n出发
可以+1,-1或者*2,问至少多少步可以到达k

爆搜爆搜爆搜

自己T了之后看到个题解说剪枝,吓死了
细看发现就是个边界判定,不要出界就好

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int N=1000000;
struct node{
int x,s;//x=location,s=step
node(int x=0,int s=0):x(x),s(s){};
};
int i,n,k;
bool vis[N];
queue<node>q;
int main(){
//freopen("fuck.in","r",stdin);
for (;scanf("%d%d",&n,&k)==2;){
if (n>=k)printf("%d\n",n-k);
else{
memset(vis,0,sizeof(vis));
while (!q.empty())q.pop();
vis[n]=1;
for (q.push(node(n,0));!q.empty();q.pop()){
node t=q.front();
//printf("x=%d step=%d\n",t.x,t.s);
if (t.x==k)break;
if (t.x-1>=0&&!vis[t.x-1]){//left
vis[t.x-1]=1;
q.push(node(t.x-1,t.s+1));
}
if (t.x+1<=k&&!vis[t.x+1]){//right
vis[t.x+1]=1;
q.push(node(t.x+1,t.s+1));
}
if (t.x <=k&&!vis[t.x*2]){//Teleport
vis[t.x*2]=1;
q.push(node(t.x*2,t.s+1));
}
}
printf("%d\n",q.front().s);
}
}
return 0;
}

本来没什么问题
自己想秀操作压几行代码

这里写图片描述
这里写图片描述

结果把自己玩死了

这里写图片描述
这里写图片描述

下次老老实实一出个新节点就标记vis吧

这里写图片描述
这里写图片描述