Main.java

//
// It's not a Bug, It's a Feature! (Java Version)
// Christopher Vo (cvo1 at cs.gmu.edu)
//
public class Main {
  private static final class Patch {
    private int cost = 0, rp = 0, rm = 0, pp = 0, pm = 0;
  }
  private static final class Node implements Comparable<Node> {
    private int state = 0, cost = 0;
    public final int compareTo(Node o) {
      return cost - o.cost;
    }
  }
  public static void main(String[] args) {
    int prod_num = 1;
    final java.util.Scanner s = new java.util.Scanner(System.in);
    final java.util.PriorityQueue<Node> q = new java.util.PriorityQueue<Node>();
    while (s.hasNextInt()) {
      int num_b = s.nextInt();
      int num_p = s.nextInt();
      if (num_b == 0 && num_p == 0) break;
      final Patch[] pl = new Patch[num_p];
      final boolean[] v = new boolean[1 << num_b];
      for (int i = 0; i < num_p; i++) {
        pl[i] = new Patch();
        pl[i].cost = s.nextInt();
        String req = s.next();
        String pat = s.next();
        for (int j = 0; j < num_b; j++) {
          final int bit = (1 << (num_b - j - 1));
          pl[i].rm |= req.charAt(j) == '-' ? bit : 0;
          pl[i].rp |= req.charAt(j) == '+' ? bit : 0;
          pl[i].pm |= pat.charAt(j) == '-' ? bit : 0;
          pl[i].pp |= pat.charAt(j) == '+' ? bit : 0;
        }
      }
      // push initial node to queue
      q.clear();
      Node t = new Node();
      t.state = (1 << num_b) - 1;
      t.cost = 0;
      q.add(t);
      // while the queue is not empty
      while (!q.isEmpty()) {
        t = q.remove(); // pop!
        if (v[t.state]) continue; // if visited, skip
        v[t.state] = true; // visit this one
        if (t.state == 0) break; // if goal, quit
        for(Patch p : pl) {
          // if patch can be applied, apply and add result to queue
          if ((t.state & p.rp) == p.rp && (t.state & p.rm) == 0) {
            Node n = new Node();
            n.state = t.state | p.pp;
            n.state = n.state & ~(p.pm);
            n.cost = t.cost + p.cost;
            if (!v[n.state]) q.add(n);
          }
        }
      }
      System.out.format("Product %d\n", prod_num++);
      if (t.state == 0)
        System.out.format("Fastest sequence takes %d seconds.\n\n", t.cost);
      else
        System.out.format("Bugs cannot be fixed.\n\n");
    }
  }
}

p658.cpp

//
// It's not a Bug, It's a Feature!
// Christopher Vo (cvo1 at cs.gmu.edu)
//
#include <iostream>
#include <queue>
#include <cstdio>
#include <cstring>
using namespace std;
typedef unsigned int UINT;

struct patch {
  UINT cost, rp, rm, pp, pm;
};

struct node {
  UINT state, cost;
  bool operator<(const node &o) const { return cost > o.cost; }
};

int main(int argc, char * argv[])
{
  int num_b, num_p, prod_num = 1;
  while ((cin >> num_b >> num_p) && (num_b != 0 || num_p != 0)) {
    int i, j;
    patch p[num_p]; // max: 100 patches (2 KB total)
    bool v[1 << num_b]; // max: 2^20 possible states (1 MB total)
    memset(v, 0, sizeof(bool) * (1 << num_b));
    // input patches
    for (i = 0; i < num_p; i++) {
      string req, pat;
      cin >> p[i].cost >> req >> pat;
      p[i].rm = p[i].rp = p[i].pm = p[i].pp = 0;
      for (j = 0; j < num_b; j++) {
        UINT bit = (1 << (num_b - j - 1));
        p[i].rm |= req[j] == '-' ? bit : 0;
        p[i].rp |= req[j] == '+' ? bit : 0;
        p[i].pm |= pat[j] == '-' ? bit : 0;
        p[i].pp |= pat[j] == '+' ? bit : 0;
      }
    }
    // push start state into queue
    priority_queue<node> q;
    node t;
    t.state = (1 << num_b) - 1;
    t.cost = 0;
    q.push(t);
    // while queue is not empty
    while (!q.empty()) {
      // pop a state
      t = q.top();
      q.pop();
      // if visited, skip
      if (v[t.state]) continue;
      v[t.state] = true;
      // if goal, quit
      if (t.state == 0) break;
      // loop through patches
      for (i = 0; i < num_p; i++) {
        // if patch can be applied, apply it and push into queue
        if ((t.state & p[i].rp) == p[i].rp && (t.state & p[i].rm) == 0) {
          node n;
          n.state = t.state | p[i].pp;
          n.state = n.state & ~(p[i].pm);
          n.cost = t.cost + p[i].cost;
          if(!v[n.state]) q.push(n);
        }
      }
    }
    printf("Product %d\n", prod_num++);
    if (t.state == 0) printf("Fastest sequence takes %d seconds.\n\n", t.cost);
    else printf("Bugs cannot be fixed.\n\n");
  }
  return 0;
}