jcross.cpp

#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();
    }
}