poj 3414 Pots 【BFS+记录路径 】

时间：2021-01-02 07:24:13

//yy:昨天看着这题突然有点懵，不知道怎么记录路径，然后交给房教了，，，然后默默去写另一个bfs，想清楚思路后花了半小时写了120+行的代码然后出现奇葩的CE，看完FAQ改了之后又WA了。然后第一次用对拍去找特殊数据折腾到十二点半终于AC，最后只想感叹没有仔细读题，没办法啊看着英语略烦躁，不扯了，那个题题解不想写了，回到这题。。。今天中午还是花了四十分钟写了这题（好慢啊orz），感觉，啊为什么别人可以一下子就写出来，我却想不到怎么写呢！！！

poj 3414 Pots  【BFS】

题意：两个给定容量a, b的杯子，有倒满水，倒光水，互相倒水三个操作，直到任意一个杯子中的水达到指定容量c为止。输出操作步骤。（a,b,c≤100）

题解：六个方向的bfs，加上100*100的记录路径。

 #include <iostream>

 #include <cstdio>

 #include <algorithm>

 #include <cstring>

 #include <queue>

 #define CLR(a,b) memset((a),(b),sizeof((a)))

 using namespace std;

 typedef long long ll;

 const int inf = 0x3f3f3f3f;

 const int N = ;

 string s[] = {"impossible","FILL(1)","FILL(2)","DROP(1)","DROP(2)","POUR(1,2)","POUR(2,1)"};

 int a, b, c;

 typedef struct Node {

     int x, y;

     Node(int _x = , int _y = ):x(_x),y(_y){}

 }node;

 node g[N][N];//存储上一步的状态

 int Do[N][N];//记录操作

 bool vis[N][N];//标记

 node bfs() {

     CLR(g, -);   CLR(vis, );

     node t;

     int i = , j = ;

     queue<node> q;

     q.push(Node(, ));

     while(!q.empty()) {

         t = q.front();  q.pop();

         if(t.x == c || t.y == c) return t;

         vis[t.x][t.y] = ;

         if(t.x != a && !vis[a][t.y]) { q.push(Node(a, t.y)); Do[a][t.y] = ; g[a][t.y] = t; }

         if(t.y != b && !vis[t.x][b]) { q.push(Node(t.x, b)); Do[t.x][b] = ; g[t.x][b] = t; }

         if(t.x && !vis[][t.y]) { q.push(Node(, t.y)); Do[][t.y] = ; g[][t.y] = t; }

         if(t.y && !vis[t.x][]) { q.push(Node(t.x, )); Do[t.x][] = ; g[t.x][] = t; }

         if(!vis[i = max(, t.x + t.y - b)][j = min(b, t.x + t.y)]) { q.push(Node(i, j)); Do[i][j] = ; g[i][j] = t; }

         if(!vis[i = min(a, t.x + t.y)][j = max(, t.x + t.y - a)]) { q.push(Node(i, j)); Do[i][j] = ; g[i][j] = t; }

     }

     return Node(, );

 }

 void dfs(const node & d, const int & p) {

     if(d.x + d.y == ) {

         if(p) { cout << p << endl; } else { cout << s[] << endl; }

         return;

     }

     dfs(g[d.x][d.y], p+);

     cout << s[Do[d.x][d.y]] << endl;

 }

 int main() {

     scanf("%d%d%d", &a, &b, &c);

     node ans = bfs();

     dfs(ans, );

     return ;

 }

相关文章