POJ3414 Pots 倒水问题（BFS）

求最少步骤 最短路径用BFS
此博客中代码会WA 但是我不知道为什么 跪求指点
正解见：https://blog.csdn.net/weixin_44339734/article/details/104170937

两个壶A、B互相倒水 最终要达到其中一个水壶中有C值的水 无法达到输出‘impossible’

Sample Input
3 5 4
Sample Output
6
FILL(2)
POUR(2,1)
DROP(1)
POUR(2,1)
FILL(2)
POUR(2,1)

错 误 示 范

#include 
#include 
#include 
#include 
#include using namespace std;struct Node{int potA;int potB;string path;int step;
};int visited[100][100];int main()
{int A,B,C;bool found;queue<Node> tempQueue;scanf("%d %d %d",&A,&B,&C);if(C==0){cout << 0 <<endl;return 0;}memset(visited,0,10000*sizeof(int));Node startNode1,startNode2;startNode1.potA=A;startNode1.potB=0;startNode1.path = "FILL(1)\n";startNode1.step=1;startNode2.potA=0;startNode2.potB=B;startNode2.path = "FILL(2)\n";startNode2.step=1;visited[A][0]=1;visited[0][B]=1;if(C==A){cout << 1<<endl<<startNode1.path;return 0;}if(C==B){cout << 1<<endl<<startNode2.path;return 0;}while(!tempQueue.empty())tempQueue.pop();tempQueue.push(startNode1);tempQueue.push(startNode2);found = false;while(!tempQueue.empty()){Node tempNode = tempQueue.front();tempQueue.pop();// A->Bif(tempNode.potA!=0){//dropAif(visited[0][tempNode.potB]==0){visited[0][tempNode.potB]=1;Node newNode;newNode.potA=0;newNode.potB = tempNode.potB;newNode.path = tempNode.path+"DROP(1)\n";newNode.step = tempNode.step+1;tempQueue.push(newNode);if(newNode.potB==C||newNode.potA==C){cout << newNode.step << "\n"<<newNode.path;found = true;break;}			}// B remain > Aif((B-tempNode.potB)>tempNode.potA){if(visited[0][tempNode.potB+tempNode.potA]==0){visited[0][tempNode.potB+tempNode.potA]=1;Node newNode;newNode.potA=0;newNode.potB = tempNode.potB+tempNode.potA;newNode.path = tempNode.path+"POUR(1,2)\n";newNode.step = tempNode.step+1;tempQueue.push(newNode);if(newNode.potB==C||newNode.potA==C){cout << newNode.step << "\n"<<newNode.path;found = true;break;}}	}// B remain <=Aif((B-tempNode.potB)<=tempNode.potA){if(visited[tempNode.potA-B+tempNode.potB][B]==0){visited[tempNode.potA-B+tempNode.potB][B]=1;Node newNode;newNode.potA = tempNode.potA-B+tempNode.potB;newNode.potB = B;newNode.path = tempNode.path+"POUR(1,2)\n";newNode.step = tempNode.step+1;tempQueue.push(newNode);if(newNode.potB==C||newNode.potA==C){cout << newNode.step << "\n"<<newNode.path;found = true;break;}}}}//B->Aif(tempNode.potB!=0){//dropBif(visited[tempNode.potA][0]==0){visited[tempNode.potA][0]=1;Node newNode;newNode.potA = tempNode.potA;newNode.potB=0;newNode.path = tempNode.path+"DROP(2)\n";newNode.step = tempNode.step+1;tempQueue.push(newNode);if(newNode.potB==C||newNode.potA==C){cout << newNode.step << "\n"<<newNode.path;found = true;break;}			}// A remain > Bif((A-tempNode.potA)>tempNode.potB){if(visited[tempNode.potB+tempNode.potA][0]==0){visited[tempNode.potB+tempNode.potA][0]=1;Node newNode;newNode.potA = tempNode.potB+tempNode.potA;newNode.potB = 0;newNode.path = tempNode.path+"POUR(2,1)\n";newNode.step = tempNode.step+1;tempQueue.push(newNode);if(newNode.potA==C||newNode.potB==C){cout << newNode.step << "\n"<<newNode.path;found = true;break;}}	}// A remain <=Bif((A-tempNode.potA)<=tempNode.potB){if(visited[A][tempNode.potB-A+tempNode.potA]==0){visited[A][tempNode.potB-A+tempNode.potA]=1;Node newNode;newNode.potA = A;newNode.potB = tempNode.potB-A+tempNode.potA;newNode.path = tempNode.path+"POUR(2,1)\n";newNode.step = tempNode.step+1;tempQueue.push(newNode);if(newNode.potB==C||newNode.potA==C){cout << newNode.step << "\n"<<newNode.path;found = true;break;}}}}// fillAif(tempNode.potA!=A){if(visited[A][tempNode.potB]==0){visited[A][tempNode.potB]=1;Node newNode;newNode.potA = A;newNode.potB = tempNode.potB;newNode.path = tempNode.path+"FILL(1)\n";newNode.step = tempNode.step+1;tempQueue.push(newNode);if(newNode.potA==C||newNode.potB==C){cout << newNode.step << "\n"<<newNode.path;found = true;break;}}}// fillBif(tempNode.potB!=B){if(visited[tempNode.potA][B]==0){visited[tempNode.potA][B]=1;Node newNode;newNode.potA = tempNode.potA;newNode.potB = B;newNode.path = tempNode.path+"FILL(2)\n";newNode.step = tempNode.step+1;tempQueue.push(newNode);if(newNode.potA==C||newNode.potB==C){cout << newNode.step << "\n"<<newNode.path;found = true;break;}}}}if(!found)cout << "impossible"<<endl;return 0;}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！