Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

这题剧毒 要注意找到路径后要反转一下 最后是因为找到pour1->2的条件写对的

Posted by adameta0730 at 2019-07-21 22:19:28 on Problem 3414
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator