| ||||||||||
| 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 | |||||||||
这题剧毒 要注意找到路径后要反转一下 最后是因为找到pour1->2的条件写对的#include <bits/stdc++.h>
using namespace std;
const int maxn = 110;
int a, b, c; //容量
bool vis[maxn][maxn]; // a和b的状态
struct node {
int a, b;
int step;
int father;
int i;
node(int _a, int _b, int _step, int _father, int _i)
: a(_a), b(_b), step(_step), father(_father), i(_i) {}
node() {}
};
vector<node> closeTable;
// 0-5分别对应
// fill1 fill2 drop1 drop2 pour12 pour21
string m[6] = {"FILL(1)", "FILL(2)", "DROP(1)",
"DROP(2)", "POUR(1,2)", "POUR(2,1)"};
queue<node> q;
bool bfs(int maxa, int maxb) {
int cnt = -1;
q.push(node(0, 0, 0, -1, -1));
while (!q.empty()) {
node temp = q.front();
q.pop();
closeTable.push_back(temp);
cnt++; //这里是为了close表 能够正确的寻找父亲
if (temp.a == c || temp.b == c) {
return true;
}
if (!vis[maxa][temp.b]) {
vis[maxa][temp.b] = true;
q.push(node(maxa, temp.b, temp.step + 1, cnt, 0));
}
if (!vis[temp.a][maxb]) {
vis[temp.a][maxb] = true;
q.push(node(temp.a, maxb, temp.step + 1, cnt, 1));
}
if (!vis[0][temp.b]) {
vis[0][temp.b] = true;
q.push(node(0, temp.b, temp.step + 1, cnt, 2));
}
if (!vis[temp.a][0]) {
vis[temp.a][0] = true;
q.push(node(temp.a, 0, temp.step + 1, cnt, 3));
}
if (temp.a >= maxb - temp.b &&
!vis[temp.a - (maxb - temp.b)][maxb]) //能够装满b
{
vis[temp.a - (maxb - temp.b)][maxb] = true;
q.push(node(temp.a - (maxb - temp.b), maxb, temp.step + 1, cnt, 4));
} else if (temp.a + temp.b <= maxb &&
!vis[0][temp.a + temp.b]) { //把a清空了
vis[0][temp.a + temp.b] = true;
q.push(node(0, temp.a + temp.b, temp.step + 1, cnt, 4));
}
if (temp.b >= maxa - temp.a &&
!vis[maxa][temp.b - (maxa - temp.a)]) { //能装满a
vis[maxa][temp.b - (maxa - temp.a)] = true;
q.push(node(maxa, temp.b - (maxa - temp.a), temp.step + 1, cnt, 5));
} else if (temp.a + temp.b <= maxa && !vis[temp.a + temp.b][0]) { // b空了
vis[temp.a + temp.b][0] = true;
q.push(node(temp.a + temp.b, 0, temp.step + 1, cnt, 5));
}
}
return false;
}
int main(int argc, char const *argv[]) {
cin >> a >> b >> c;
vis[0][0] = true;
if (bfs(a, b)) {
// for (int i = 0; i < closeTable.size(); i++) {
// cout << closeTable[i].a << " " << closeTable[i].b
// << " fa:" << closeTable[i].father <<" i:"<<closeTable[i].i<< endl;
// }
int index = closeTable.size() - 1;
cout << closeTable[index].step << endl;
vector<string> res;
while (closeTable[index].father != -1) {
res.push_back(m[closeTable[index].i]);
index = closeTable[index].father;
}
for (int i = res.size() - 1; i >= 0; i--) {
cout<<res[i]<<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