问题描述
问题分析
看博客里面搜索分类下的题目也不是很多……
为什么感觉做过好多搜索题了……-.-
这一题还是很简单的
(话说突然感觉这种搜索都不难 设置好条件之后就不用动脑子了)
首先若要可以倒可乐S&1==0也就是S应为偶数
然后当N==M时 很显然只需要一次
其余的进行搜索
终止条件是S里面有S/2的饮料 N M中较大的那个里有剩下的一半饮料
然后……搜索就好了
为了剪枝
建个数组记录下当前的状态是否已经搜索过
这代码的亮点我感觉还是
通过数组来保存数据
可以达到用循环来找寻的目的
而不用一个一个地写
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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
| #include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
int rflag[105][105][105];
struct node {
int x[3];
int cnt;
} t;
int main() {
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
int l[3];
while(scanf("%d %d %d",&l[0],&l[1],&l[2]),l[0]||l[1]||l[2]) {
memset(rflag,0,sizeof(rflag));
if(l[0]&1)
printf("NO\n");
else if(l[1]==l[2])
printf("1\n");
else {
if(l[1]>l[2]) {
int t=l[1];
l[1]=l[2];
l[2]=t;
}
queue<node>q;
t.x[0]=l[0];
t.x[1]=0;
t.x[2]=0;
t.cnt=0;
q.push(t);
bool flag=false;
int res;
while(!q.empty()) {
t=q.front();
if(rflag[t.x[0]][t.x[1]][t.x[2]]) {
q.pop();
continue;
}
rflag[t.x[0]][t.x[1]][t.x[2]]=1;
if(t.x[0]==l[0]/2&&t.x[1]==0&&t.x[2]==l[0]/2) {
flag=true;
res=t.cnt;
break;
}
for(int i=0; i<3; i++) {
if(t.x[i]>0) {
for(int j=0; j<3; j++) {
if(i==j||t.x[j]==l[j])
continue;
node tq=t;
if(t.x[i]+t.x[j]>l[j]) {
tq.x[i]=t.x[i]+t.x[j]-l[j];
tq.x[j]=l[j];
tq.cnt=t.cnt+1;
q.push(tq);
} else {
tq.x[i]=0;
tq.x[j]=t.x[i]+t.x[j];
tq.cnt=t.cnt+1;
q.push(tq);
}
}
}
}
q.pop();
}
if(flag)
printf("%d\n",res);
else
printf("NO\n");
}
}
return 0;
}
|
题目地址:【杭电】[1495]非常可乐