题意:输入s,m,n三个数,分别代表可乐,和两个杯子,三个容器可以互相倒,问能不能把s平分,能的话输出最小步数,不能就输出NO。
思路:BFS,一共有六种情况,s->m(s向m里倒),s->n,m->n,m->s,n->s,n->m。用BFS暴搜,从队列里每取出一个,就用这六种情况扩展一次,并把步数加一,直到搜到终止状态。
STL版本:
#include<iostream> #include<queue> #define MAX 105 using namespace std; struct point { int x,y,z; int step; }; bool vis[MAX][MAX][MAX]; int s,m,n; void change_ab(int &a,int &b,int ra,int rb)//a倒入b { int left=rb-b;//看b差多少满 if(left>0&&a>0) { if(a>=left) { b=rb; a-=left; } else { b+=a; a=0; } } } int bfs() { memset(vis,0,sizeof(vis)); queue<point> Q; int ta,tb,tc; int half=s/2; point start,node; vis[s][0][0]=1; start.x=s; start.y=0; start.z=0; start.step=0; Q.push(start); while(!Q.empty()) { start=Q.front();Q.pop(); ta=start.x; tb=start.y; tc=start.z; if((ta==half&&tb==half)||(tb==half&&tc==half)||(ta==half&&tc==half)) { //printf("%d %d %d ~~%d\n",ta,tb,tc,start.step) ; return start.step; } change_ab(ta,tb,s,m); if(!vis[ta][tb][tc]) { vis[ta][tb][tc]=1; node.x=ta; node.y=tb; node.z=tc; node.step=start.step+1; Q.push(node); //printf("%d %d %d %d\n",ta,tb,tc,node.step); } ta=start.x; tb=start.y; tc=start.z; change_ab(ta,tc,s,n); if(!vis[ta][tb][tc]) { vis[ta][tb][tc]=1; node.x=ta; node.y=tb; node.z=tc; node.step=start.step+1; Q.push(node); //printf("%d %d %d %d\n",ta,tb,tc,node.step); } ta=start.x; tb=start.y; tc=start.z; change_ab(tb,tc,m,n); if(!vis[ta][tb][tc]) { vis[ta][tb][tc]=1; node.x=ta; node.y=tb; node.z=tc; node.step=start.step+1; Q.push(node); //printf("%d %d %d %d\n",ta,tb,tc,node.step); } ta=start.x; tb=start.y; tc=start.z; change_ab(tb,ta,m,s); if(!vis[ta][tb][tc]) { vis[ta][tb][tc]=1; node.x=ta; node.y=tb; node.z=tc; node.step=start.step+1; Q.push(node); //printf("%d %d %d %d\n",ta,tb,tc,node.step); } ta=start.x; tb=start.y; tc=start.z; change_ab(tc,ta,n,s); if(!vis[ta][tb][tc]) { vis[ta][tb][tc]=1; node.x=ta; node.y=tb; node.z=tc; node.step=start.step+1; Q.push(node); //printf("%d %d %d %d\n",ta,tb,tc,node.step); } ta=start.x; tb=start.y; tc=start.z; change_ab(tc,tb,n,m); if(!vis[ta][tb][tc]) { vis[ta][tb][tc]=1; node.x=ta; node.y=tb; node.z=tc; node.step=start.step+1; Q.push(node); //printf("%d %d %d %d\n",ta,tb,tc,node.step); } } return 0; } int main() { while(scanf("%d%d%d",&s,&m,&n)!=EOF) { if(s==0&&m==0&&n==0) break; if(s%2!=0) {printf("NO\n"); continue;} if(bfs()!=0) printf("%d\n",bfs()); else printf("NO\n"); } }
数组模拟版本:
#include<iostream> #include<queue> #define MAX 105 using namespace std; struct point { int x,y,z; int step; }; bool vis[MAX][MAX][MAX]; point p[1000100]; int s,m,n; void change_ab(int &a,int &b,int ra,int rb)//a倒入b { int left=rb-b; if(left>0&&a>0) { if(a>=left) { b=rb; a-=left; } else { b+=a; a=0; } } } int bfs() { memset(vis,0,sizeof(vis)); // queue<point> Q; int ta,tb,tc; long front,rear; int half=s/2; point start,node; vis[s][0][0]=1; front=0;rear=0; start.x=s; start.y=0; start.z=0; start.step=0; p[rear++]=start; while(rear!=front) { //start=Q.front();Q.pop(); //ta=start.x; //tb=start.y; //tc=start.z; start=p[front++]; if((start.x==half&&start.y==half)||(start.y==half&&start.z==half)||(start.x==half&&start.z==half)) { //printf("%d %d %d ~~%d\n",ta,tb,tc,start.step) ; return start.step; } ta=start.x; tb=start.y; tc=start.z; change_ab(ta,tb,s,m); if(!vis[ta][tb][tc]) { vis[ta][tb][tc]=1; node.x=ta; node.y=tb; node.z=tc; node.step=start.step+1; p[rear++]=node; //printf("%d %d %d %d\n",ta,tb,tc,node.step); } ta=start.x; tb=start.y; tc=start.z; change_ab(ta,tc,s,n); if(!vis[ta][tb][tc]) { vis[ta][tb][tc]=1; node.x=ta; node.y=tb; node.z=tc; node.step=start.step+1; p[rear++]=node; //printf("%d %d %d %d\n",ta,tb,tc,node.step); } ta=start.x; tb=start.y; tc=start.z; change_ab(tb,tc,m,n); if(!vis[ta][tb][tc]) { vis[ta][tb][tc]=1; node.x=ta; node.y=tb; node.z=tc; node.step=start.step+1; p[rear++]=node; //printf("%d %d %d %d\n",ta,tb,tc,node.step); } ta=start.x; tb=start.y; tc=start.z; change_ab(tb,ta,m,s); if(!vis[ta][tb][tc]) { vis[ta][tb][tc]=1; node.x=ta; node.y=tb; node.z=tc; node.step=start.step+1; p[rear++]=node; //printf("%d %d %d %d\n",ta,tb,tc,node.step); } ta=start.x; tb=start.y; tc=start.z; change_ab(tc,ta,n,s); if(!vis[ta][tb][tc]) { vis[ta][tb][tc]=1; node.x=ta; node.y=tb; node.z=tc; node.step=start.step+1; p[rear++]=node; //printf("%d %d %d %d\n",ta,tb,tc,node.step); } ta=start.x; tb=start.y; tc=start.z; change_ab(tc,tb,n,m); if(!vis[ta][tb][tc]) { vis[ta][tb][tc]=1; node.x=ta; node.y=tb; node.z=tc; node.step=start.step+1; p[rear++]=node; //printf("%d %d %d %d\n",ta,tb,tc,node.step); } } return 0; } int main() { while(scanf("%d%d%d",&s,&m,&n)!=EOF) { if(s==0&&m==0&&n==0) break; if(s%2!=0) {printf("NO\n"); continue;} if(bfs()!=0) printf("%d\n",bfs()); else printf("NO\n"); } }