Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
好复杂啊、想了好久~~贴码留念下......#include <iostream> #include <cmath> #include <cstdio> #include <cstring> #include <cstdlib> #include <stack> #include <queue> #include <vector> #include <algorithm> #include <string> typedef long long LL; typedef unsigned long long ULL; using namespace std; const int MAXN = 100; int MaxA, MaxB, C;//Pots A的最大容量;Pots B的最大容量;目标容量 C; const string OPERA[] = {"-1", "FILL(1)", "FILL(2)", "DROP(1)", "DROP(2)", "POUR(1,2)", "POUR(2,1)"};//分别代表六种可能的操作 int visit[MAXN + 7][MAXN + 7];//visit[i][j] = 1表示Pots A的水量为 i, Pots B的水量为 j这一状态已经出现过. struct Status { int NowA;//此时A中的水量 int NowB;//此时B中的水量 int step;//到达此状态的操作次数 string order;//到达此状态的所有操作 }; Status BFS() { memset(visit, 0, sizeof(visit)); Status fist;//初始状态 fist.NowA = fist.NowB = fist.step = 0; fist.order = ""; queue<Status> Qu; Qu.push(fist);//从初始状态开始BFS visit[0][0] = 1; while(!Qu.empty()) { Status temp = Qu.front(); Qu.pop(); if(temp.NowA == C || temp.NowB == C) return temp;//找到目标状态 Status nex; if(temp.NowA != MaxA) {//A中水不为满,可执行操作1 --> FILL(1) nex.NowA = MaxA, nex.NowB = temp.NowB, nex.step = temp.step + 1;//执行操作1之后,状态发生变化,记录即可 if(nex.step == 1) nex.order = temp.order + OPERA[1]; else nex.order = temp.order + "\n" + OPERA[1]; if(!visit[nex.NowA][nex.NowB]) {//这个状态没有发生过 Qu.push(nex); visit[nex.NowA][nex.NowB] = 1; } } if(temp.NowB != MaxB) {//B中水不为满,可执行操作2 --> FILL(2) nex.NowA = temp.NowA, nex.NowB = MaxB, nex.step = temp.step + 1; if(nex.step == 1) nex.order = temp.order + OPERA[2]; else nex.order = temp.order + "\n" + OPERA[2]; if(!visit[nex.NowA][nex.NowB]) { Qu.push(nex); visit[nex.NowA][nex.NowB] = 1; } } if(temp.NowA != 0) {//A中水不为空,可执行操作3 --> DROP(1) nex.NowA = 0, nex.NowB = temp.NowB, nex.step = temp.step + 1; if(nex.step == 1) nex.order = temp.order + OPERA[3]; else nex.order = temp.order + "\n" + OPERA[3]; if(!visit[nex.NowA][nex.NowB]) { Qu.push(nex); visit[nex.NowA][nex.NowB] = 1; } } if(temp.NowB != 0) {//B中水不为空,可执行操作4 --> DROP(2) nex.NowA = temp.NowA, nex.NowB = 0, nex.step = temp.step + 1; if(nex.step == 1) nex.order = temp.order + OPERA[4]; else nex.order = temp.order + "\n" + OPERA[4]; if(!visit[nex.NowA][nex.NowB]) { Qu.push(nex); visit[nex.NowA][nex.NowB] = 1; } } if(temp.NowA != 0 && temp.NowB != MaxB) {//A中水不为空,且B中水不为满,可执行操作5 --> POUR(1,2) nex.NowA = max(0, temp.NowA - (MaxB - temp.NowB)), nex.NowB = min(MaxB, temp.NowA + temp.NowB); nex.step = temp.step + 1; if(nex.step == 1) nex.order = temp.order + OPERA[5]; else nex.order = temp.order + "\n" + OPERA[5]; if(!visit[nex.NowA][nex.NowB]) { Qu.push(nex); visit[nex.NowA][nex.NowB] = 1; } } if(temp.NowB != 0 && temp.NowA != MaxA) {//B中水不为空,且A中水不为满,可执行操作6 --> POUR(2,1) nex.NowA = min(MaxA, temp.NowA + temp.NowB), nex.NowB = max(0, temp.NowB - (MaxA - temp.NowA)); nex.step = temp.step + 1; if(nex.step == 1) nex.order = temp.order + OPERA[6]; else nex.order = temp.order + "\n" + OPERA[6]; if(!visit[nex.NowA][nex.NowB]) { Qu.push(nex); visit[nex.NowA][nex.NowB] = 1; } } } return fist;//没找到答案 } int main() { ios_base::sync_with_stdio(false); cin >> MaxA >> MaxB >> C; Status ans = BFS(); if(ans.NowA == C || ans.NowB == C) cout << ans.step << endl << ans.order << endl; else cout << "impossible" << endl; return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator