1 条题解
-
0
#include<bits/stdc++.h>//这是deque+map版本 using namespace std; struct node{int a[4],dep,kt;}; deque<node>Q;//多组数据用双端队列,因为有clear()函数 map<int,bool>V;//相当于bool v[](避免定义v数组的大小),可以这样用v[x]=1或v[x]=0,x是int类型 //判重用map容器,如果康托值超过1亿,则需采用map容器判重 int A[4],k; int kt(node no)//a[i]最大值为100,是3位数 { return no.a[1]*1000000+no.a[2]*1000+no.a[3]; } bool ok(node no) { for(int i=1;i<=3;i++) if(no.a[i]==k) return 1; return 0; } int main() { while( scanf("%d%d%d%d",&A[1],&A[2],&A[3],&k)!=EOF) { if(A[1]==k) {printf("yes\n0\n"); continue;} node stno=node{{0,A[1],0,0},0,0};stno.kt=kt(stno); V.clear();V[stno.kt]=1;//因为是多组数据,所以每次都要清空 Q.clear();Q.push_back(stno); bool bk=0; while(!Q.empty()) { for(int i=1;i<=3;i++)for(int j=1;j<=3;j++) if(i!=j&&Q.front().a[i]>0) { node no=Q.front(); int t=A[j]-no.a[j]; if(no.a[i]>=t){ no.a[j]+=t; no.a[i]-=t;} else { no.a[j]+=no.a[i]; no.a[i]=0; } no.dep=Q.front().dep+1; no.kt=kt(no); if(V[no.kt]==0) { V[no.kt]=1; Q.push_back(no); if(ok(no)==1){bk=1;break;} } } Q.pop_front(); if(bk==1)break; } if(bk==1) printf("yes\n%d\n",Q.back().dep); else printf("no\n"); } return 0; }
- 1
信息
- ID
- 89
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 7
- 标签
- 递交数
- 309
- 已通过
- 61
- 上传者