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