| 1 | bool handle_solution(vi rows) { return false; } |
| 2 | struct exact_cover { |
| 3 | struct node { |
| 4 | node *l, *r, *u, *d, *p; |
| 5 | int row, col, size; |
| 6 | node(int _row, int _col) : row(_row), col(_col) { |
| 7 | size = 0; l = r = u = d = p = NULL; } }; |
| 8 | int rows, cols, *sol; |
| 9 | bool **arr; |
| 10 | node *head; |
| 11 | exact_cover(int _rows, int _cols) |
| 12 | : rows(_rows), cols(_cols), head(NULL) { |
| 13 | arr = new bool*[rows]; |
| 14 | sol = new int[rows]; |
| 15 | rep(i,0,rows) |
| 16 | arr[i] = new bool[cols], memset(arr[i], 0, cols); } |
| 17 | void set_value(int row, int col, bool val = true) { |
| 18 | arr[row][col] = val; } |
| 19 | void setup() { |
| 20 | node ***ptr = new node**[rows + 1]; |
| 21 | rep(i,0,rows+1) { |
| 22 | ptr[i] = new node*[cols]; |
| 23 | rep(j,0,cols) |
| 24 | if (i == rows || arr[i][j]) ptr[i][j] = new node(i,j); |
| 25 | else ptr[i][j] = NULL; } |
| 26 | rep(i,0,rows+1) { |
| 27 | rep(j,0,cols) { |
| 28 | if (!ptr[i][j]) continue; |
| 29 | int ni = i + 1, nj = j + 1; |
| 30 | while (true) { |
| 31 | if (ni == rows + 1) ni = 0; |
| 32 | if (ni == rows || arr[ni][j]) break; |
| 33 | ++ni; } |
| 34 | ptr[i][j]->d = ptr[ni][j]; |
| 35 | ptr[ni][j]->u = ptr[i][j]; |
| 36 | while (true) { |
| 37 | if (nj == cols) nj = 0; |
| 38 | if (i == rows || arr[i][nj]) break; |
| 39 | ++nj; } |
| 40 | ptr[i][j]->r = ptr[i][nj]; |
| 41 | ptr[i][nj]->l = ptr[i][j]; } } |
| 42 | head = new node(rows, -1); |
| 43 | head->r = ptr[rows][0]; |
| 44 | ptr[rows][0]->l = head; |
| 45 | head->l = ptr[rows][cols - 1]; |
| 46 | ptr[rows][cols - 1]->r = head; |
| 47 | rep(j,0,cols) { |
| 48 | int cnt = -1; |
| 49 | rep(i,0,rows+1) |
| 50 | if (ptr[i][j]) cnt++, ptr[i][j]->p = ptr[rows][j]; |
| 51 | ptr[rows][j]->size = cnt; } |
| 52 | rep(i,0,rows+1) delete[] ptr[i]; |
| 53 | delete[] ptr; } |
| 54 | #define COVER(c, i, j) \ |
| 55 | c->r->l = c->l, c->l->r = c->r; \ |
| 56 | for (node *i = c->d; i != c; i = i->d) \ |
| 57 | for (node *j = i->r; j != i; j = j->r) \ |
| 58 | j->d->u = j->u, j->u->d = j->d, j->p->size--; |
| 59 | #define UNCOVER(c, i, j) \ |
| 60 | for (node *i = c->u; i != c; i = i->u) \ |
nothing calls this directly
no outgoing calls
no test coverage detected