1 条题解
-
0
C :
#include<stdio.h> #include<stdlib.h> char cz[6][20]={"fill A","fill B","empty A","empty B","pour A B","pour B A"}; int op[10000];//记录步骤 int count; int n,ca,cb;//需求量,a容量,b容量 typedef struct { int a;//当前a的容量 int b;//当前b的容量 int step;//层数 }node; typedef struct { node data[10000]; int front; int rear; }cqueue;//存放水杯状态的队列 int isempty(cqueue*a) { if(a->front==a->rear) { return 1; } else { return 0; } } void empty(cqueue*a) { a->rear=a->front=-1; } void push(cqueue*a,node x) { a->rear++; a->data[a->rear]=x; } void pop(cqueue*a) { a->front++; } int**hash;//记录是否达到过两瓶水当前容量这个状态; cqueue num;//存放状态节点的队列 cqueue*numm=# node Node;//充当节点临时变量 node**hash2;//记录达到两瓶水当前容量这个状态的前一个状态; int**hash3;//记录达到两瓶水当前容量这个状态的前一个操作; void print() { int i; for(i=0;i<count;i++) { if(op[i]==0) { printf("fill A\n"); } if(op[i]==1) { printf("fill B\n"); } if(op[i]==2) { printf("empty A\n"); } if(op[i]==3) { printf("empty B\n"); } if(op[i]==4) { printf("pour A B\n"); } if(op[i]==5) { printf("pour B A\n"); } } printf("success\n"); }//用于输出路径，暂时还没用上 void bfs() { node temp;//当前队首元素 int i; while(!isempty(numm))//当队列不为空 { temp=numm->data[numm->front+1];//取出队首元素 pop(numm);//出队 if(temp.b==n)//如果满足条件，函数结束 { Node.a=temp.a; Node.b=temp.b; Node.step=temp.step; return ; } for(i=0;i<6;i++)//6种情况分别选择 { if(i==0)//fill A { Node.a=ca; Node.b=temp.b;//给完成倒水操作的相邻状态赋值 Node.step=temp.step+1;//相邻节点层数加1 if(hash[Node.a][Node.b]==0)//如果这个操作结束后的状态已经进入过队列，就不把这种情况入队,否则，进入并把标志置1 { push(numm,Node); hash[Node.a][Node.b]=1; hash2[Node.a][Node.b]=temp; hash3[Node.a][Node.b]=0; } } if(i==1)//fill B { Node.a=temp.a; Node.b=cb; Node.step=temp.step+1; if(hash[Node.a][Node.b]==0) { push(numm,Node); hash[Node.a][Node.b]=1; hash2[Node.a][Node.b]=temp; hash3[Node.a][Node.b]=1; } } if(i==2)//empty A { Node.a=0; Node.b=temp.b; Node.step=temp.step+1; if(hash[Node.a][Node.b]==0) { push(numm,Node); hash[Node.a][Node.b]=1; hash2[Node.a][Node.b]=temp; hash3[Node.a][Node.b]=2; } } if(i==3)//empty B { Node.a=temp.a; Node.b=0; Node.step=temp.step+1; if(hash[Node.a][Node.b]==0) { push(numm,Node); hash[Node.a][Node.b]=1; hash2[Node.a][Node.b]=temp; hash3[Node.a][Node.b]=3; } } if(i==4)//pour A B { if(temp.a>cb-temp.b) { Node.b=cb; Node.a=temp.a-cb+temp.b; Node.step=temp.step+1; if(hash[Node.a][Node.b]==0) { push(numm,Node); hash[Node.a][Node.b]=1; hash2[Node.a][Node.b]=temp; hash3[Node.a][Node.b]=4; } } else { Node.b=temp.a+temp.b; Node.a=0; Node.step=temp.step+1; if(hash[Node.a][Node.b]==0) { push(numm,Node); hash[Node.a][Node.b]=1; hash2[Node.a][Node.b]=temp; hash3[Node.a][Node.b]=4; } } } if(i==5)//pour B A { if(temp.b>ca-temp.a) { Node.a=ca; Node.b=temp.b-ca+temp.a; Node.step=temp.step+1; if(hash[Node.a][Node.b]==0) { push(numm,Node); hash[Node.a][Node.b]=1; hash2[Node.a][Node.b]=temp; hash3[Node.a][Node.b]=5; } } else { Node.a=temp.b+temp.a; Node.b=0; Node.step=temp.step+1; if(hash[Node.a][Node.b]==0) { push(numm,Node); hash[Node.a][Node.b]=1; hash2[Node.a][Node.b]=temp; hash3[Node.a][Node.b]=5; } } } }//6种情况的节点均已入队列,该节点的相邻节点遍历结束 } } int main() { int i,j; while(scanf("%d %d %d",&ca,&cb,&n)!=EOF) { empty(numm);//清空队列 hash=(int**)malloc(sizeof(int*)*(ca+1)); hash2=(node**)malloc(sizeof(node*)*(ca+1)); hash3=(int**)malloc(sizeof(int*)*(ca+1)); for(i=0;i<ca+1;i++) { hash[i]=(int*)malloc(sizeof(int)*(cb+1)); hash2[i]=(node*)malloc(sizeof(node)*(cb+1)); hash3[i]=(int*)malloc(sizeof(int)*(cb+1)); } for(i=0;i<ca+1;i++) { for(j=0;j<cb+1;j++) { hash[i][j]=0;//将所有标志位清零 } } Node.a=0; Node.b=0; hash[0][0]=1; Node.step=0;//更新开始状态 push(numm,Node); bfs(); count=Node.step; for(i=count-1;i>=0;i--) { op[i]=hash3[Node.a][Node.b]; Node=hash2[Node.a][Node.b]; } print(); //printf("%d\n",Node.step); } return 0; }C++ :
#include<cstdio> #include<cstring> #include<queue> using namespace std; struct JUG { int ca,cb,a[1000],k; }start,head,tail; char s[6][9]={"fill A","fill B","empty A","empty B","pour A B","pour B A"}; int ca,cb,n,v[1001][1001]; void bfs() { memset(v,0,sizeof(v)); queue<JUG> q; q.push(start); v[start.ca][start.cb]=1; while(!q.empty()) { head=q.front(); q.pop(); if(head.ca==n||head.cb==n) return; tail=head; tail.ca=ca; if(!v[tail.ca][tail.cb]) { v[tail.ca][tail.cb]=1; tail.a[tail.k]=0; tail.k++; q.push(tail); } tail=head; tail.cb=cb; if(!v[tail.ca][tail.cb]) { v[tail.ca][tail.cb]=1; tail.a[tail.k]=1; tail.k++; q.push(tail); } tail=head; tail.ca=0; if(!v[tail.ca][tail.cb]) { v[tail.ca][tail.cb]=1; tail.a[tail.k]=2; tail.k++; q.push(tail); } tail=head; tail.cb=0; if(!v[tail.ca][tail.cb]) { v[tail.ca][tail.cb]=1; tail.a[tail.k]=3; tail.k++; q.push(tail); } tail=head; if(tail.ca&&tail.cb<cb) { if(tail.ca<=cb-tail.cb) { tail.cb+=tail.ca; tail.ca=0; if(!v[tail.ca][tail.cb]) { v[tail.ca][tail.cb]=1; tail.a[tail.k]=4; tail.k++; q.push(tail); } } else { tail.ca-=cb-tail.cb; tail.cb=cb; if(!v[tail.ca][tail.cb]) { v[tail.ca][tail.cb]=1; tail.a[tail.k]=4; tail.k++; q.push(tail); } } } tail=head; if(tail.cb&&tail.ca<ca) { if(tail.cb<=ca-tail.ca) { tail.ca=+tail.cb; tail.cb=0; if(!v[tail.ca][tail.cb]) { v[tail.ca][tail.cb]=1; tail.a[tail.k]=5; tail.k++; q.push(tail); } } else { tail.cb-=ca-tail.ca; tail.ca=ca; if(!v[tail.ca][tail.cb]) { v[tail.ca][tail.cb]=1; tail.a[tail.k]=5; tail.k++; q.push(tail); } } } } } int main() { int i; while(scanf("%d%d%d",&ca,&cb,&n)!=EOF) { start.ca=start.cb=start.k=0; bfs(); for(i=0;i<head.k;i++) puts(s[head.a[i]]); puts("success"); } return 0; }
admin
LV 2
SU
@ 2025-4-7 21:19:29
- 1