POJ3414 Pots BFS搜素
题意:通过题目给出的三种操作,让任意一个杯子中的水到达一定量
分析:两个杯子最大容量是100,所以开个100*100的数组记录状态,最多1w个状态,所以复杂度很低,然后记录一下路径就好
注:代码写残了,我也不会写好看的那种,罪过罪过..QAQ
#include<cstdio> #include<algorithm> #include<iostream> #include<cstring> #include<cmath> #include<map> #include<queue> #include<stdlib.h> #include<string> #include<set> using namespace std; typedef long long LL; const int maxn=105; const int INF=0x3f3f3f3f; struct Point { int x,y,op,s; } mp[maxn][maxn],o,t; int p[maxn][maxn]; queue<Point>q; void print(int x,int y) { if(x==-1)return; print(mp[x][y].x,mp[x][y].y); if(mp[x][y].op==1)printf("FILL(%d) ",mp[x][y].s); else if(mp[x][y].op==2)printf("DROP(%d) ",mp[x][y].s); else if(mp[x][y].op==3)printf("POUR(%d,%d) ",mp[x][y].s,3-mp[x][y].s); } int main() { int a,b,c,flag=0; scanf("%d%d%d",&a,&b,&c); for(int i=0; i<=a; ++i) for(int j=0; j<=b; ++j) mp[i][j].op=-1; mp[a][0].op=1,mp[a][0].s=1; mp[0][b].op=1,mp[0][b].s=2; mp[a][0].x=-1,mp[0][b].x=-1; o.x=a,o.y=0; q.push(o); o.x=0,o.y=b; q.push(o); p[a][0]=p[0][b]=1; while(!q.empty()) { o=q.front(); q.pop(); if(o.x==c||o.y==c) { t=o; flag=1; break; } if(o.x<a) { if(mp[a][o.y].op==-1) { mp[a][o.y].op=1; mp[a][o.y].s=1; mp[a][o.y].x=o.x; mp[a][o.y].y=o.y; t.x=a,t.y=o.y; p[t.x][t.y]=p[o.x][o.y]+1; q.push(t); } } if(o.y<b) { if(mp[o.x][b].op==-1) { mp[o.x][b].op=1; mp[o.x][b].s=2; mp[o.x][b].x=o.x; mp[o.x][b].y=o.y; t.x=o.x,t.y=b; p[t.x][t.y]=p[o.x][o.y]+1; q.push(t); } } if(o.x) { if(mp[0][o.y].op==-1) { mp[0][o.y].op=2; mp[0][o.y].s=1; mp[0][o.y].x=o.x; mp[0][o.y].y=o.y; t.x=0,t.y=o.y; p[t.x][t.y]=p[o.x][o.y]+1; q.push(t); } int cha=b-o.y; if(o.x<=cha) t.y=o.y+o.x,t.x=0; else t.y=b,t.x=o.x-cha; if(mp[t.x][t.y].op==-1) { mp[t.x][t.y].op=3; mp[t.x][t.y].s=1; mp[t.x][t.y].x=o.x; mp[t.x][t.y].y=o.y; p[t.x][t.y]=p[o.x][o.y]+1; q.push(t); } } if(o.y) { if(mp[o.x][0].op==-1) { mp[o.x][0].op=2; mp[o.x][0].s=2; mp[o.x][0].x=o.x; mp[o.x][0].y=o.y; t.x=o.x,t.y=0; p[t.x][t.y]=p[o.x][o.y]+1; q.push(t); } int cha=a-o.x; if(o.y<=cha) t.x=o.y+o.x,t.y=0; else t.x=a,t.y=o.y-cha; if(mp[t.x][t.y].op==-1) { mp[t.x][t.y].op=3; mp[t.x][t.y].s=2; mp[t.x][t.y].x=o.x; mp[t.x][t.y].y=o.y; p[t.x][t.y]=p[o.x][o.y]+1; q.push(t); } } } if(flag)printf("%d ",p[t.x][t.y]),print(t.x,t.y); else printf("impossible "); return 0; }