pku 3414 Pots 经典BFS

迈不过友情╰ 2022-08-10 00:44 107阅读 0赞

1. 基本的状态转移是很好找的.

2. 难点是判重和状态的保存.

判重我用的是visited\[x\]\[y\]二维数组, A为容量x, B为容量y时标记已访问;当再次A为容量x, B为容量y时,不再重复搜索.

至于状态的保存我用的是一个结构体

struct Step  
\{  
int cnt; //一走步数  
int prex, prey; //前一步的分别容量prex, prey  
int preflag; //前一步到本步骤执行的操作标志  
\};

后面的实现就不赘述了.

\#include <iostream> \#include <queue> \#include <stack> using namespace std; int A, B, C; struct Pots \{ int x, y; Pots(int xx, int yy)\{x = xx; y = yy;\} \}; struct Step \{ int cnt; int prex, prey; int preflag; \}; bool visited\[102\]\[102\]; Step step\[102\]\[102\]; queue<Pots> q; int endx, endy; void saveState(int x, int y, int prex, int prey, int flag) \{ q.push(Pots(x, y)); step\[x\]\[y\].cnt = step\[prex\]\[prey\].cnt+1; step\[x\]\[y\].prex = prex; step\[x\]\[y\].prey = prey; step\[x\]\[y\].preflag = flag; \} int bfs() \{ memset(visited, 0, sizeof(visited)); memset(step, 0, sizeof(step)); q.push(Pots(0, 0)); while(!q.empty()) \{ Pots v = q.front(); if(v.x == C || v.y == C) \{ endx = v.x, endy = v.y; break; \} q.pop(); visited\[v.x\]\[v.y\] = true; if(v.x < A && !visited\[A\]\[v.y\]) //fill a saveState(A, v.y, v.x, v.y, 0); if(v.y < B && !visited\[v.x\]\[B\]) //fill b saveState(v.x, B, v.x, v.y, 1); if(v.x > 0 && !visited\[0\]\[v.y\]) //drop a saveState(0, v.y, v.x, v.y, 2); if(v.y > 0 && !visited\[v.x\]\[0\]) //drop b saveState(v.x, 0, v.x, v.y, 3); if(v.x > 0) // pour a to b \{ if(v.x < B-v.y && !visited\[0\]\[v.x+v.y\]) saveState(0, v.x+v.y, v.x, v.y, 4); else if(v.x >= B-v.y && !visited\[v.x-(B-v.y)\]\[B\]) saveState(v.x-(B-v.y), B, v.x, v.y, 5); \} if(v.y > 0) //pour b to a \{ if(v.y < A-v.x && !visited\[v.x+v.y\]\[0\]) saveState(v.x+v.y, 0, v.x, v.y, 6); else if(v.y >= A-v.x && !visited\[A\]\[v.y-(A-v.x)\]) saveState(A, v.y-(A-v.x), v.x, v.y, 7); \} \} return step\[endx\]\[endy\].cnt; \} void findPath() \{ stack<int> s; int x = endx, y = endy; while(!(x ==0 && y == 0)) \{ s.push(step\[x\]\[y\].preflag); int tempx = step\[x\]\[y\].prex; int tempy = step\[x\]\[y\].prey; x = tempx, y = tempy; \} while(!s.empty()) \{ int v = s.top(); s.pop(); switch(v) \{ case 0: printf("FILL(1)/n"); break; case 1: printf("FILL(2)/n"); break; case 2: printf("DROP(1)/n"); break; case 3: printf("DROP(2)/n"); break; case 4: case 5: printf("POUR(1,2)/n"); break; case 6: case 7: printf("POUR(2,1)/n"); break; \} \} \} int main() \{ scanf("%d%d%d", &A, &B, &C); int ret = bfs(); if(ret) \{ printf("%d/n", ret); findPath(); \} else printf("impossible/n"); return 0; \}

本题集BFS的最值问题和保存状态问题于一身,不失为一道好题!

另一种方法:

采用的是在队列中直接保存以前的状态, 效率没有上面的方式高, 但是对于状态的保存, 很有参考价值.

struct Pots  
\{  
int x, y; //当前x, y量  
int op; //到本步的操作  
int pre; //前一状态在队列中的位置  
Pots() \{\}  
Pots(int xx, int yy, int \_op, int \_pre)\{x = xx; y = yy; op = \_op; pre = \_pre;\}  
\};

\#include <iostream> \#include <cstdio> \#include <cstring> using namespace std; \#define MAX 10000 template<class T> class Queue \{ T q\[MAX\]; int \_front, \_rear; public: Queue()\{\_front = \_rear = -1;\} void push(const T& t) \{ q\[++\_rear\] = t; \} int pop() \{ return ++\_front; \} T& front() \{ return q\[\_front+1\]; \} bool empty() const \{ return (\_front == \_rear); \} int top() const \{ return \_rear; \} const T& operator\[\](int index) const \{ return q\[index\]; \} \}; int A, B, C; struct Pots \{ int x, y; //当前x, y量 int op; //到本步的操作 int pre; //前一状态在队列中的位置 Pots() \{\} Pots(int xx, int yy, int \_op, int \_pre)\{x = xx; y = yy; op = \_op; pre = \_pre;\} \}; Queue<Pots> q; bool visited\[102\]\[102\]; int bfs() \{ memset(visited, 0, sizeof(visited)); q.push(Pots(0, 0, -1, -1)); visited\[0\]\[0\] = true; while(!q.empty()) \{ Pots v = q.front(); int pre = q.pop(); if(v.x == C || v.y == C) return pre; if(v.x < A && !visited\[A\]\[v.y\]) //fill a \{ q.push(Pots(A, v.y, 0, pre)); visited\[A\]\[v.y\] = true; \} if(v.y < B && !visited\[v.x\]\[B\]) //fill b \{ q.push(Pots(v.x, B, 1, pre)); visited\[v.x\]\[B\] = true; \} if(v.x > 0 && !visited\[0\]\[v.y\]) //drop a \{ q.push(Pots(0, v.y, 2, pre)); visited\[0\]\[v.y\] = true; \} if(v.y > 0 && !visited\[v.x\]\[0\]) //drop b \{ q.push(Pots(v.x, 0, 3, pre)); visited\[v.x\]\[0\] = true; \} if(v.x > 0) // pour a to b \{ if(v.x < B-v.y && !visited\[0\]\[v.x+v.y\]) \{ q.push(Pots(0, v.x+v.y, 4, pre)); visited\[0\]\[v.x+v.y\] = true; \} else if(v.x >= B-v.y && !visited\[v.x-(B-v.y)\]\[B\]) \{ q.push(Pots(v.x-(B-v.y), B, 5, pre)); visited\[v.x-(B-v.y)\]\[B\] = true; \} \} if(v.y > 0) //pour b to a \{ if(v.y < A-v.x && !visited\[v.x+v.y\]\[0\]) \{ q.push(Pots(v.x+v.y, 0, 6, pre)); visited\[v.x+v.y\]\[0\] = true; \} else if(v.y >= A-v.x && !visited\[A\]\[v.y-(A-v.x)\]) \{ q.push(Pots(A, v.y-(A-v.x), 7, pre)); visited\[A\]\[v.y-(A-v.x)\] = true; \} \} \} return -1; \} int seq\[MAX\]; void output(int k) \{ int cnt = 0; while(q\[k\].pre != -1) \{ seq\[cnt++\] = q\[k\].op; k = q\[k\].pre; \} printf("%d/n", cnt); for(int i = cnt-1; i >= 0; i--) switch(seq\[i\]) \{ case 0: printf("FILL(1)/n"); break; case 1: printf("FILL(2)/n"); break; case 2: printf("DROP(1)/n"); break; case 3: printf("DROP(2)/n"); break; case 4: case 5: printf("POUR(1,2)/n"); break; case 6: case 7: printf("POUR(2,1)/n"); break; \} \} int main() \{ scanf("%d%d%d", &A, &B, &C); int ret = bfs(); if(ret == -1) printf("impossible/n"); else output(ret); return 0; \}