[kuangbin带你飞]专题一 简单搜索H---Pots

# 题目链接： https://vjudge.net/problem/POJ-3414 # 题意： 用两个瓶子称出指定的水 有三种操作： 1. 用水盛满瓶子 1. 倒掉瓶子里的水 1. 将一个瓶子里的水倒到另一个瓶子里 # 思路： 使用bfs对状态进行扩展，用二维数组判重，各种数组保存参数，用dfs进行回溯搜索路径。 此题需要考虑的地方比较多，适合用来训练搜索算法。 # AC代码： ```cpp #include<iostream> #include<algorithm> #include<cstring> #include<cstdio> using namespace std; const int maxn = 105; pair<int,int>que[ maxn * maxn]; int dis[maxn*maxn],vis[maxn][maxn]; int from[maxn*maxn],opt[maxn*maxn],optwhat[maxn*maxn]; int a,b,c; int lft,rit; void check(int nowa,int nowb,int op,int which) { if(vis[nowa][nowb]) return; vis[nowa][nowb]=1; from[rit]=lft; dis[rit]=dis[lft]+1; opt[rit]=op; optwhat[rit]=which; que[rit++]=make_pair(nowa,nowb); } int bfs() { que[rit++]=make_pair(0,0); vis[0][0]=1; while(lft<rit) { int ai=que[lft].first; int bi=que[lft].second; if(ai==c||bi==c) return lft; check(a,bi,1,1); check(ai,b,1,2); check(0,bi,2,1); check(ai,0,2,2); if(ai > b - bi) check(ai - b + bi, b,3,1); else check(0,ai+bi,3,1); if(bi > a - ai ) check(a,bi-a+ai,3,2); else check(ai+bi,0,3,2); lft++; } return 0; } void print(int now) { if(from[now]>0) print(from[now]); if(opt[now]==1) printf("FILL(%d)\n",optwhat[now]); else if (opt[now]==2) printf("DROP(%d)\n",optwhat[now]); else if(opt[now]==3) printf("POUR(%d,%d)\n",optwhat[now],3-optwhat[now]); } int main() { while(~scanf("%d%d%d",&a,&b,&c)) { int ans=0; memset(dis,0,sizeof(dis)); memset(from,0,sizeof(from)); memset(vis,0,sizeof(vis)); memset(opt,0,sizeof(opt)); memset(optwhat,0,sizeof(optwhat)); lft=rit=0; if(ans=bfs()) { printf("%d\n",dis[ans]); print(ans); } else printf("impossible\n"); } return 0; } /* 3 4 2 4 f1 p12 f1 p12 */ ```