题目链接：点击打开链接
题目大意：略。
解题思路：记忆化搜索，对每个状态都有六种情况：
- 把A倒满
- 把B倒满
- 把A倒光
- 把B倒光
- 把A倒进B
- 把B倒进A
六个情况直接搜索就可以了...当然dfs是会超时的，需要用记忆化搜索。
AC 代码
#include<bits/stdc++.h> #include<cmath> #define mem(a,b) memset(a,b,sizeof a); #define INF 0x3f3f3f3f using namespace std; typedef long long ll; typedef pair<int,int> pii; queue<pii> 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; }
