Skip to content

Instantly share code, notes, and snippets.

@maksverver
Created August 22, 2015 20:54
Show Gist options
  • Save maksverver/57259ab745aa3aa8d457 to your computer and use it in GitHub Desktop.
Save maksverver/57259ab745aa3aa8d457 to your computer and use it in GitHub Desktop.
#include <algorithm>
#include <assert.h>
#include <stdlib.h>
#include <vector>
#include <string>
#include <utility>
#include <iostream>
using namespace std;
typedef unsigned long long uint64;
struct Cell {
int row, col;
uint64 bit;
vector<const Cell*> neighbours;
};
const int max_cells = 37;
static vector<Cell> cells;
static int bits;
namespace {
bool valid(int row, int col) {
return row >= 0 && row < 7 && col >= 0 && col < 7 && abs((row - 3) - (col - 3)) <= 3;
}
bool centre(int row, int col) { return row == 3 && col == 3; }
int search(int i, uint64 red_mask);
int search_red(int i, uint64 red_mask) {
int res = 0;
for (const Cell* cell : cells[i].neighbours) {
if ((cell->bit & red_mask) == 0) ++res;
}
return res + search(i + 1, red_mask | cells[i].bit);
}
int search_blue(int i, uint64 red_mask) {
int res = 2;
for (const Cell*cell : cells[i].neighbours) {
if ((cell->bit & red_mask) != 0) ++res;
}
return res + search(i + 1, red_mask);
}
int search(int i, uint64 red_mask) {
if (i == cells.size()) return 0;
static int memo[1 << 8][max_cells];
assert(i < max_cells);
int &m = memo[red_mask >> max(0, i - 8)][i];
if (m > 0) return m;
int res = search_blue(i, red_mask);
if (cells[i].bit) res = max(res, search_red(i, red_mask));
return m = res;
}
} // namespace
int main() {
for (int r = 0; r < 7; ++r) {
for (int c = 0; c < 7; ++c) {
if (valid(r, c)) {
Cell cell = { r, c, 0 };
if (!centre(r, c)) cell.bit = uint64(1) << bits++;
cells.push_back(cell);
}
}
}
for (int j = 0; j < cells.size(); ++j) {
for (int i = 0; i < j; ++i) {
int dr = cells[i].row - cells[j].row;
int dc = cells[i].col - cells[j].col;
if (abs(dr) <= 1 && abs(dc) <= 1 && abs(dr - dc) <= 1) {
cells[j].neighbours.push_back(&cells[i]);
}
}
}
cout << search(0, 0) << endl;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment