termites.cc

#include <iostream>
#include <queue>

const int INFESTED = 0x80;
const int PASSABLE = 0x08;

struct pos {
  int x, y;
};

struct Map {
  int w, h;
  pos source;
  char grid[15][15];

  /* Safely get the tile at (X, Y). */
  char get(int x, int y) const {
    return (x >= 0 && x < w && y >= 0 && y < h) ? grid[x][y] : '\0';
  }

  /* Returns true if the bunkers are currently safe. */
  bool safe() {
    std::queue<pos> queue{};
    queue.push(source);
    while (!queue.empty()) {
      pos p = queue.front();
      queue.pop();
      char c = get(p.x, p.y);
      if (c & PASSABLE && !(c & INFESTED)) {
        if (c == 'o') {
          clear();
          return false;
        } else {
          grid[p.x][p.y] |= INFESTED;
          queue.push(pos{p.x + 1, p.y + 0});
          queue.push(pos{p.x - 1, p.y + 0});
          queue.push(pos{p.x + 0, p.y + 1});
          queue.push(pos{p.x + 0, p.y - 1});
        }
      }
    }
    clear();
    return true;
  }

  /* Attempt to solve the map for COUNT walls. */
  bool solve(int count) {
    if (count == 0) return safe();
    for (int y = 0; y < h; y++) {
      for (int x = 0; x < w; x++) {
        if (grid[x][y] == '-') {
          if ((get(x - 1, y + 0) != '-') ||
              (get(x + 1, y + 0) != '-') ||
              (get(x + 0, y + 1) != '-') ||
              (get(x + 0, y - 1) != '-')) {
            grid[x][y] = '@';
            if (solve(count - 1)) {
              return true;
            } else {
              grid[x][y] = '-';
            }
          }
        }
      }
    }
    return false;
  }

  /* Remove all infestation markers. */
  void clear() {
    for (int y = 0; y < h; y++) {
      for (int x = 0; x < w; x++) {
        grid[x][y] &= ~INFESTED;
      }
    }
  }
};

std::istream &operator>>(std::istream &in, Map &map) {
  in >> map.h >> map.w;
  for (int y = 0; y < map.h; y++) {
    for (int x = 0; x < map.w; x++) {
      in >> map.grid[x][y];
      if (map.grid[x][y] == '*') map.source = {x, y};
    }
  }
  return in;
}

std::ostream &operator<<(std::ostream &out, const Map map) {
  for (int y = 0; y < map.h; y++) {
    for (int x = 0; x < map.w; x++) {
      out << map.grid[x][y];
    }
    out << std::endl;
  }
  return out;
}

int main() {
  Map map;
  std::cin >> map;
  int wallcount = -1;
  do {
    wallcount++;
    std::cerr << "Trying " << wallcount << " walls ..." << std::endl;
  } while (!map.solve(wallcount));
  std::cout << wallcount << std::endl << map;
  return 0;
}