| ||||||||||
| 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