BFS与水罐灌水问题

三个水桶,最大容量为10L, 7L, 4L。

初始状态为,10L,0L,0L。 即,第一个是满的,后两个是空的。

可进行的操作:把某个水桶的水倒入另一个水桶中,直到这两个水桶的某一个满了或者空了。 比如 (10,0,0) -> (3,7,0)

问:至少进行几次操作,使得某一个水桶的水为2。就是说,怎么倒来倒去,能量出2L水来。

这是一个很古典的智力题。

解:

我们先画一个圆圈,写上(10,0,0),代表水桶的初始状态。然后把它能通过一步操作转移到哪些状态,也画出来,用线连起来。如此反复。最终我们会得到一个很大的无向图,每个节点都是一种状态,每条边代表一次倒水操作。我们要做的,是从(10,0,0)这个节点开始,进行广度优先搜索。

/**
* 三个水桶,最大容量为10,7,4
* 初始状态为,10,0,0
* 可进行的操作:把某个水桶的水倒入另一个水桶中,直到这两个水桶的某一个满了或者空了。
* 问:至少进行几次操作,使得某一个水桶的水为2
*/
#include <iostream>
#include <queue>
#include <algorithm>
#include <unordered_map>
#include <string.h>

struct Node {
  int state[3];
  Node(int x, int y, int z) {
    state[0] = x;
    state[1] = y;
    state[2] = z;
  }
  Node(const Node& n) { memcpy(state, n.state, sizeof(state)); }

  bool operator==(const Node& n) const {
    return !memcmp(state, n.state, sizeof(state));
  }

  bool isFound(int n) const {
    return state[0] == n || state[1] == n || state[2] == n;
  }
};

struct NodeHash {
  size_t operator()(const Node* n) const {
    size_t ret = n->state[0];
    ret = ret * 37 + n->state[1];
    ret = ret * 37 + n->state[2];
    return ret;
  }
};

struct NodeEquals {
  bool operator()(const Node* l, const Node* r) const { return *l == *r; }
};

static int cap[3] = { 10, 7, 4 };

static Node* move(size_t i, size_t j, const Node* n) {
  int m = std::min(n->state[i], cap[j] - n->state[j]);
  if (!m) return NULL;
  Node* n1 = new Node(*n);
  n1->state[i] -= m;
  n1->state[j] += m;
  return n1;
}

std::vector<Node> dfs_search(int x, int y, int z) {
  std::queue<Node*> q;
  typedef std::unordered_map<Node*, Node*, NodeHash, NodeEquals> MAP;
  MAP visited;
  {
    Node* init = new Node(x, y, z);
    q.push(init);
    visited[init] = NULL;
  }
  std::vector<Node> ret;
  while (!q.empty()) {
    Node* cur = q.front();
    q.pop();
    for (int i = 0; i != 3; ++i) {
      for (int j = 0; j != 3; ++j) {
        if (i == j) continue;
        Node* n = move(i, j, cur);
        if (!n) continue;
        if (n->isFound(2)) {
          ret.push_back(*n);
          delete n;
          while (true) {
            ret.push_back(*cur);
            MAP::iterator iter = visited.find(cur);
            if (iter == visited.end()) break;
            cur = iter->second;
            if (!cur) break;
          }
          goto end;
        }
        if (visited.find(n) == visited.end()) {
          visited[n] = cur;
          q.push(n);
        } else
          delete n;
      }
    }
  }
end:
  for (MAP::iterator iter = visited.begin(); iter != visited.end(); ++iter) {
    delete iter->first;
  }
  return ret;
}

int main() {
  std::vector<Node> ret = dfs_search(10, 7, 3);
  for (size_t i = ret.size(); i != 0; --i) {
    Node& n = ret[i - 1];
    std::cout << n.state[0] << " " << n.state[1] << " " << n.state[2] << "\n";
  }
  return 0;
}

此博客中的热门博文

少写代码,多读别人写的代码

在windows下使用llvm+clang

tensorflow distributed runtime初窥