Skip to content

Instantly share code, notes, and snippets.

@Izaron Izaron/jcross.cpp Secret
Created Aug 7, 2018

Embed
What would you like to do?
#include <iostream>
#include <string.h>
#include <assert.h>
#include <cmath>
#include <map>
#include <set>
#include <unordered_map>
#include <vector>
#include <utility>
#include <algorithm>
#include <limits.h>
using namespace std;
typedef long long int ll;
typedef vector<int> vint;
typedef pair<int, int> pii;
typedef tuple<int, int, int> tt;
class OneLineSolver {
public:
bool Init(int side_length, int color_count);
bool UpdateState(const std::vector<std::pair<int, int>>& groups,
std::vector<int>& cells);
private:
const int kMaxColorsCount = 31;
const int kMaxPreferredColorsCount = 11;
bool CheckMaxColorsOverflow(int color_count);
void CheckMaxPreferredColorsOverflow(int color_count);
void AllocMemory(int side_length);
bool CanPlaceColor(const std::vector<int>& cells, int color, int lbound,
int rbound);
void SetPlaceColor(int color, int lbound, int rbound);
bool CanFill(const std::vector<std::pair<int, int>>& groups,
const std::vector<int>& cells, int current_group,
int current_cell);
std::vector<std::vector<int>> cache_;
std::vector<std::vector<int>> calculated_fill_;
std::vector<int> result_cells_;
int cache_count_;
};
bool OneLineSolver::Init(int side_length, int color_count) {
if (!CheckMaxColorsOverflow(color_count)) {
return false;
}
CheckMaxPreferredColorsOverflow(color_count);
AllocMemory(side_length);
return true;
}
bool OneLineSolver::CheckMaxColorsOverflow(int color_count) {
if (color_count > kMaxColorsCount) {
return false;
}
return true;
}
void OneLineSolver::CheckMaxPreferredColorsOverflow(int color_count) {
if (color_count > kMaxPreferredColorsCount) {
// what?
}
}
void OneLineSolver::AllocMemory(int side_length) {
cache_.resize(side_length + 1);
calculated_fill_.resize(side_length + 1);
for (int i = 0; i < cache_.size(); ++i) {
cache_[i].resize(side_length + 1);
calculated_fill_[i].resize(side_length + 1);
}
result_cells_.resize(side_length);
cache_count_ = 0;
}
bool OneLineSolver::CanPlaceColor(const vector<int>& cells, int color,
int lbound, int rbound) {
if (rbound >= cells.size()) {
return false;
}
int mask = 1 << color;
for (int i = lbound; i <= rbound; ++i) {
if (!(cells[i] & mask)) {
return false;
}
}
return true;
}
void OneLineSolver::SetPlaceColor(int color, int lbound, int rbound) {
for (int i = lbound; i <= rbound; ++i) {
result_cells_[i] |= (1 << color);
}
}
bool OneLineSolver::CanFill(const vector<pair<int, int>>& groups,
const vector<int>& cells, int current_group = 0, int current_cell = 0) {
if (current_cell == cells.size()) {
return current_group == groups.size();
}
int cached = cache_[current_group][current_cell];
int answer = calculated_fill_[current_group][current_cell];
if (cached == cache_count_) {
return answer;
}
answer = 0;
if (CanPlaceColor(cells, 0, current_cell, current_cell) &&
CanFill(groups, cells, current_group, current_cell + 1)) {
SetPlaceColor(0, current_cell, current_cell);
answer = 1;
}
if (current_group < groups.size()) {
int current_color = groups[current_group].second;
int lbound = current_cell;
int rbound = current_cell + groups[current_group].first - 1;
bool can_place = CanPlaceColor(cells, current_color, lbound, rbound);
bool place_white = false; // It may be required to place a white cell
// right after the current group
int next_cell = rbound + 1; // The cell to continue solve the puzzle
// Check whether we are to put a white cell after the group
if (can_place) {
// If the next group color is the same, then we should place
// a WHITE cell
if (current_group + 1 < groups.size() &&
groups[current_group + 1].second == current_color) {
place_white = true;
can_place = CanPlaceColor(cells, 0, next_cell, next_cell);
next_cell++;
}
}
if (can_place) {
// If after placement the puzzle can be solved, remember this
if (CanFill(groups, cells, current_group + 1, next_cell)) {
answer = 1;
SetPlaceColor(current_color, lbound, rbound);
if (place_white) {
SetPlaceColor(0, rbound + 1, rbound + 1);
}
}
}
}
calculated_fill_[current_group][current_cell] = answer;
cache_[current_group][current_cell] = cache_count_;
return answer;
}
bool OneLineSolver::UpdateState(const vector<std::pair<int, int>>& groups,
vector<int>& cells) {
cache_count_++;
fill(result_cells_.begin(), result_cells_.begin() + cells.size(), 0);
if (!CanFill(groups, cells)) {
return false;
}
copy(result_cells_.begin(), result_cells_.begin() + cells.size(),
cells.begin());
return true;
}
struct Solver {
int n, m;
vector<vector<int>> row_masks;
vector<vector<int>> col_masks;
vector<vector<pair<int, int>>> row_groups;
vector<vector<pair<int, int>>> col_groups;
int64_t UpdateCellValues() {
uint64_t sum = 0;
for (int row = 0; row < n; row++) {
for (int col = 0; col < m; col++) {
row_masks[row][col] &= col_masks[col][row];
col_masks[col][row] &= row_masks[row][col];
sum += row_masks[row][col];
}
}
return sum;
}
bool UpdateGroupsState(OneLineSolver& solver, vector<int8_t>& dead,
vector<vector<pair<int, int>>>& groups, vector<vector<int>>& masks) {
int len = groups.size();
int extra_move_count = 0;
for (int i = 0; i < len; i++) {
if (!dead[i]) {
if (!solver.UpdateState(groups[i], masks[i])) {
return false;
}
bool is_dead = true;
for (auto num : masks[i]) {
if (__builtin_popcount(num) != 1) {
is_dead = false;
break;
}
}
dead[i] = is_dead;
}
}
return true;
}
bool UpdateState(OneLineSolver& solver, vector<int8_t>& dead_rows,
vector<int8_t>& dead_cols) {
if (!UpdateGroupsState(solver, dead_rows, row_groups, row_masks)) {
return false;
}
if (!UpdateGroupsState(solver, dead_cols, col_groups, col_masks)) {
return false;
}
return true;
}
bool PlaceRandom() {
for (int i = 0; i < n; i++) {
for (int z = 0; z < m; z++) {
if (row_masks[i][z] == 3) {
row_masks[i][z] = 1;
return true;
}
}
}
return false;
}
void ReadAndSolve() {
scanf("%d%d", &n, &m);
row_groups.resize(n);
col_groups.resize(m);
for (int i = 0; i < n; i++) {
int cnt = 0;
while (true) {
scanf("%d", &cnt);
if (cnt == 0) {
break;
}
row_groups[i].push_back({cnt, 1});
}
}
for (int i = 0; i < m; i++) {
int cnt = 0;
while (true) {
scanf("%d", &cnt);
if (cnt == 0) {
break;
}
col_groups[i].push_back({cnt, 1});
}
}
int color_count = 2;
row_masks.resize(n);
for (int row = 0; row < n; row++) {
row_masks[row].resize(m, (1 << color_count) - 1);
}
col_masks.resize(m);
for (int col = 0; col < m; col++) {
col_masks[col].resize(n, (1 << color_count) - 1);
}
OneLineSolver solver;
solver.Init(max(n, m), color_count);
vector<int8_t> dead_rows(n);
vector<int8_t> dead_cols(m);
int64_t prev_sum = LLONG_MAX;
while (true) {
if (!UpdateState(solver, dead_rows, dead_cols)) {
if (!PlaceRandom()) {
break;
}
}
int64_t curr_sum = UpdateCellValues();
if (curr_sum == prev_sum) {
if (!PlaceRandom()) {
break;
}
}
prev_sum = curr_sum;
}
for (int i = 0; i < n; i++) {
for (int z = 0; z < m; z++) {
if (row_masks[i][z] == 3) {
throw 0;
} else if (row_masks[i][z] == 2) {
printf("#");
} else {
printf(".");
}
}
printf("\n");
}
}
};
int main() {
int t;
scanf("%d", &t);
while (t--) {
Solver s;
s.ReadAndSolve();
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.