Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #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;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement