POJ【3414】Pots（倒水问题+打印路径）

题目链接http://poj.org/problem?id3414分析这道题属于倒水问题思想不变不过在此之上还需要打印路径需要在节点当中存储操作o还需要记录每一个节点的父亲。#includeiostream #includecstdio #includecstring #includequeue #includevector using namespace std; const int N 100 10; int pot[2],c,vis[N][N]; char path[][10] {FILL(1),DROP(1),POUR(1,2),FILL(2),DROP(2),POUR(2,1)}; struct Node { int v[2],step,o; bool operator (const Node b) const { return step b.step; } }; Node p[N][N]; void print_path(Node u) { vectorNode nodes; //倒序追溯到初始节点 for(;;) { if(u.o -1) break; nodes.push_back(u); u p[u.v[0]][u.v[1]]; } for(int i nodes.size() - 1; i 0; i--) { int o nodes[i].o; printf(%s\n,path[o]); } } bool bfs() { priority_queueNode q; Node start; start.v[0] 0,start.v[1] 0,start.step 0,start.o -1; q.push(start); vis[0][0] 1; while(!q.empty()) { Node u q.top();q.pop(); for(int i 0; i 2; i)//i表示杯子 for(int j 0; j 3; j) {//j表示三种操作 Node u2; memcpy(u2,u,sizeof(u)); if(j 0) u2.v[i] pot[i];//倒满 else if(j 1) u2.v[i] 0;//倒空 else {//倒给另一个杯子 int k 1 ^ i; if(u2.v[i] 0 || u2.v[k] pot[k]) continue; int amount min(pot[k],u2.v[i] u2.v[k]) - u2.v[k];//倒满或倒空 u2.v[i] - amount; u2.v[k] amount; } u2.step 1; if(i 0) u2.o j;//记录此次的操作 else u2.o 3 j; if(!vis[u2.v[0]][u2.v[1]]) {//两个水量可以唯一确定一种状态 p[u2.v[0]][u2.v[1]] u;//存储父亲节点 vis[u2.v[0]][u2.v[1]] 1; if(u2.v[0] c || u2.v[1] c) {//终点状态 printf(%d\n,u2.step); print_path(u2);//打印路径 return true; } q.push(u2); } } } return false; } int main() { scanf(%d%d%d,pot[0],pot[1],c); if(!bfs()) printf(impossible\n); return 0; }