真的水
这道题,一看,很明显就是Bfs\
因为求最少步数,就是求结果在搜索树上的最小层数
用Bfs,其分层的结构特点,意味着层数最小且为所在层中所有结果最左边的结果最先遍历到,正好可以求最短步数
对于Bfs我习惯性写法就是定义一个struct,记录状态+层数.如果状态数小,可以建一个标志数组ed,push时先判断是否遍历过,这样队列size就最多只有状态数了
定义状态为{_x,_y},表示瓶x中有_x升,y中有_y升
上代码
//我喜欢手搓队列\
#include\<cstdio\>\
int ed[101][101];\
struct E{\
int x,y,step;\
}Q[10001];\
int Qt,Qw;\
int Getk(int k){\
if(k<0){\
return 10001-(-k)%10001;\
}\
return k%10001;\
}\
void push(int x,int y,int step){\
if(ed[x][y]){\
return ;\
}\
Q[Getk(Qw)].x=x;\
Q[Getk(Qw)].y=y;\
Q[Getk(Qw--)].step=step;\
}\
E pop(void){\
return Q[Getk(Qt--)];\
}\
int x,y,z;\
bool empty(void){\
return Getk(Qt)==Getk(Qw);\
}\
int Bfs(void){\
push(0,0,0);\
while(!empty()){\
E t=pop();\
ed[t.x][t.y]=1;\
//printf("%d %d %d\n",t.x,t.y,t.step);\
if(t.x==z||t.y==z){\
return t.step;\
}\
push(0,t.y,t.step+1);\
push(t.x,0,t.step+1);\
push(x,t.y,t.step+1);\
push(t.x,y,t.step+1);\
int x_c=x-t.x,y_c=y-t.y;\
push((t.x>y_c)?t.x-y_c:0,(t.x>y_c)?y:y-(y_c-t.x),t.step+1);\
push((t.y>x_c)?x:x-(x_c-t.y),(t.y>x_c)?t.y-x_c:0,t.step+1);\
}\
return -1;\
}\
int main(void){\
scanf("%d%d%d",&x,&y,&z);\
int ans=Bfs();\
if(ans!=-1){\
printf("%d\n",ans);\
}\
else{\
puts("impossible");\
}\
return 0;\
}\