本文共 1272 字，大约阅读时间需要 4 分钟。

题目链接：

题目大意：略。

解题思路：记忆化搜索，对每个状态都有六种情况：

1. 把A倒满
2. 把B倒满
3. 把A倒光
4. 把B倒光
5. 把A倒进B
6. 把B倒进A

六个情况直接搜索就可以了...当然dfs是会超时的，需要用记忆化搜索。

AC 代码

#include
   
    #include
    
     #define mem(a,b) memset(a,b,sizeof a);#define INF 0x3f3f3f3fusing namespace std;typedef long long ll;typedef pair
     
       pii;queue
      
        q;int a,b,c;int vis[110][110], dis[110][110];void init(){    while(!q.empty()) q.pop();    mem(vis,0); mem(dis,0);}int bfs(){    dis[0][0]=0; vis[0][0]=1;    q.push(make_pair(0,0));    int x,y,A,B;    while(!q.empty())    {        x=q.front().first, y=q.front().second; q.pop();        for(int i=1;i<=6;i++)        {            if(i==1) A=a, B=y;            else if(i==2) A=x, B=b;            else if(i==3) A=0, B=y;            else if(i==4) A=x, B=0;            else if(i==5) A=x+y>=b?x+y-b:0, B=x+y>=b?b:x+y;            else if(i==6) B=x+y>=a?x+y-a:0, A=x+y>=a?a:x+y;            if(!vis[A][B])            {                vis[A][B]=1;                dis[A][B]=1+dis[x][y];                if(A==c || B==c) return dis[A][B];                q.push(make_pair(A,B));            }        }    }    return 0;}int main(){    while(~scanf("%d%d%d",&a,&b,&c))    {        init();        int rs=bfs();        if(rs) printf("%d\n",rs);        else puts("impossible");    }    return 0;}
      
     
    
   

转载地址：https://lux-sun.blog.csdn.net/article/details/81082654 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！