首页 > 代码库 > SGU 126

SGU 126

2024-07-15 08:50:52   230人阅读

简单的BFS。无需任何优化。

利用一个结构体数组储存状态，三个量a,b,move分别表示A箱，B箱的球数以及移动次数。

注意对特殊情况的处理以及对不可能情况的判定：

（1）两数之差为奇数，由题意，假设a<b，则移动球数为a，差的改变量为2a。

又有最终状态的前一步是两箱数目相等，差=0，所以不可能实现。

（2）两数之差模4余2，但 初始球数都为偶数。

根据上面，类似地可以推导出不可能。

（3）出现和前面相同的情况。

- -这个就比较难处理- -数据范围在那里- - 总不能开个VIS[2^31][2^31]吧- -

一种偷懒的方法（也是苯渣用的方法）是限定一个遍历的情况数，我设的150000.

所幸SGU的数据比较弱- -（或者任一种状况都会在150000之前发生重复？未可知）

附代码：

#include "stdio.h"#include "string.h"#include "stdlib.h"const int MAXMOVE=150000;struct status{	int a,b,move;};int BFS(int A,int B){	status q[MAXMOVE+10];	int flag=0,i,j,front,rear,tmp;	front=0;rear=0;	q[0].a=A;q[0].b=B;	q[0].move=0;	if(!q[0].a||!q[0].b){		return 0;	}	if((q[0].a+q[0].b)%2){		return -1;	}	else{		while(1){			if((q[0].a%2==0)&&((q[0].a-q[0].b)%4)){				return -1;				break;			}			if(rear>MAXMOVE){				return -1;				break;			}			//printf("Front=%d,Rear=%d.\n",front,rear);			tmp=rear;			while(front<=tmp){				//printf("***front=%d.\n",front);				//Move Balls from B To A.				if(q[front].b>=q[front].a){					rear++;					q[rear].a=2*q[front].a;					q[rear].b=q[front].b-q[front].a;					//printf("******Rear = %d:  A = %d, B = %d.\n",rear,q[rear].a,q[rear].b);					//getchar();					q[rear].move=q[front].move+1;					if(!q[rear].a||!q[rear].b){						return q[rear].move;						flag=1;						break;					}				}				//Move Balls from A To B.				if(q[front].a>=q[front].b){					rear++;					q[rear].b=2*q[front].b;					q[rear].a=q[front].a-q[front].b;					q[rear].move=q[front].move+1;					//printf("*******Rear = %d:  A = %d, B = %d.\n",rear,q[rear].a,q[rear].b);					//getchar();					if(!q[rear].a||!q[rear].b){						return q[rear].move;						flag=1;						break;					}				}				front++;			}			if(flag)break;		}	}}int main(){	int ans,A,B;	scanf("%d%d",&A,&B);	ans=BFS(A,B);	printf("%d\n",ans);	return 0;}

 


联系
我们