Submission #32136330

---

Source Code Expand

#include <bits/stdc++.h>
using pii=std::pair<int,int>;
using namespace std;

const int maxnsq = 105, GRID_CHOOSE_TIMEOUT_MILLIS = 2500;

enum direction { left_bit, up_bit, right_bit, down_bit };
vector<int> direction_iterable = {left_bit, up_bit, right_bit, down_bit};
pii dirs[4] = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}};
map<pii, char> movement_to_direction_character_map = {
    {{0, -1}, 'L'}, 
    {{-1, 0}, 'U'}, 
    {{0, 1}, 'R'}, 
    {{1, 0}, 'D'}
};

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    
int n, t;

int is_valid(int x, int y)
{
    return x >= 0 && x < n && y >= 0 && y < n;
}

int is_valid_for_grid_generator(int x, int y)
{
    return is_valid(x, y) && !(x == 0 && y == 0);
}

int cnt_adjacent_connecting(int mask, int x, int y, vector<vector<int>>& grid_masks)
{
    int adj_cnt = 0;
    for(auto dir_bit : direction_iterable)
        if(mask & (1ll << dir_bit))
        {
            int nex = x + dirs[dir_bit].first;
            int ney = y + dirs[dir_bit].second;
            if(!is_valid_for_grid_generator(nex, ney))
                continue;
            int connecting_dir_bit = (dir_bit + 2) % 4;
            if(grid_masks[nex][ney] & (1ll << connecting_dir_bit))
                adj_cnt++;
        }
    return adj_cnt;
}

int has_adjacent_connecting(int x, int y, vector<vector<int>>& grid_masks)
{
    return cnt_adjacent_connecting(15, x, y, grid_masks) > 0;
}

int is_good_placement(int mask, int curx, int cury, int fromx, int fromy, vector<vector<int>>& grid_masks)
{
    int from_valid = (fromx == -1 && fromy == -1);
    for(auto dir_bit : direction_iterable)
        if(mask & (1ll << dir_bit))
        {
            int nex = curx + dirs[dir_bit].first;
            int ney = cury + dirs[dir_bit].second;
            if(nex == fromx && ney == fromy)
            {
                from_valid = 1;
                continue;
            }
            if(!is_valid_for_grid_generator(nex, ney) || grid_masks[nex][ney] != 0 || has_adjacent_connecting(nex, ney, grid_masks))
                return 0;
        }
    return from_valid;
}


pair<vector<vector<int>>, int> get_random_tree(vector<int> mask_cnts)
{
    vector<vector<int>> grid_masks(n, vector<int>(n, 0));
    int comp_sz = 0;

    vector<vector<int>> visited(n, vector<int>(n));
    vector<int> mask_order(15);
    iota(mask_order.begin(), mask_order.end(), 1);
    shuffle(mask_order.begin(), mask_order.end(), rng);
    sort(mask_order.begin(), mask_order.end(), [](const int& m1, const int& m2) {
        return __builtin_popcount(m1) > __builtin_popcount(m2);
    });

    int startx = uniform_int_distribution<int>(0, n - 1)(rng);
    int starty = uniform_int_distribution<int>(0, n - 1)(rng);
    while(startx == 0 && starty == 0)
    {
        startx = uniform_int_distribution<int>(0, n - 1)(rng);
        starty = uniform_int_distribution<int>(0, n - 1)(rng);
    }
    stack<pair<pii, pii>> s; // {{curx, cury}, {fromx, fromy}}
    s.push({{startx, starty}, {-1, -1}});
    visited[startx][starty] = 1;
    while(!s.empty())
    {
        int curx, cury, fromx, fromy;
        tie(curx, cury) = s.top().first;
        tie(fromx, fromy) = s.top().second;
        s.pop();
        for(auto mask : mask_order)
            if(mask_cnts[mask] > 0 && is_good_placement(mask, curx, cury, fromx, fromy, grid_masks))
            {
                grid_masks[curx][cury] = mask;
                mask_cnts[mask]--;
                for(auto dir_bit : direction_iterable)
                    if(mask & (1ll << dir_bit))
                    {
                        int nex = curx + dirs[dir_bit].first;
                        int ney = cury + dirs[dir_bit].second;
                        if(nex == fromx && ney == fromy)
                            continue;
                        assert(!visited[nex][ney]);
                        visited[nex][ney] = 1;
                        s.push({{nex, ney}, {curx, cury}});
                    }
                comp_sz++;
                break;
            }
    }
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            if(!(i == 0 && j == 0) && grid_masks[i][j] == 0)
                for(int mask = 1; mask <= 15; mask++)
                    if(mask_cnts[mask] > 0 && cnt_adjacent_connecting(mask, i, j, grid_masks) == 1)
                    {
                        grid_masks[i][j] = mask;
                        mask_cnts[mask]--;
                        comp_sz++;
                        break;
                    }
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            if(!(i == 0 && j == 0) && grid_masks[i][j] == 0)
                for(int mask = 1; mask <= 15; mask++)
                    if(mask_cnts[mask] > 0)
                    {
                        grid_masks[i][j] = mask;
                        mask_cnts[mask]--;
                        break;
                    }
    return {grid_masks, comp_sz};
}

void calc_shortest_path(int fromx, int fromy, vector<vector<int>>& dist, vector<vector<pii>>& from, vector<vector<int>>& fixed)
{
    assert(is_valid(fromx, fromy) && !fixed[fromx][fromy]);
    queue<pii> q;
    dist[fromx][fromy] = 0;
    q.push({fromx, fromy});
    while(!q.empty())
    {
        int curx, cury;
        tie(curx, cury) = q.front();
        q.pop();
        for(auto ne : dirs)
        {
            int nex = curx + ne.first;
            int ney = cury + ne.second;
            if(is_valid(nex, ney) && !fixed[nex][ney] && dist[curx][cury] + 1 < dist[nex][ney])
            {
                dist[nex][ney] = dist[curx][cury] + 1;
                from[nex][ney] = {curx, cury};
                q.push({nex, ney});
            }
        }
    }
}

vector<pii> recover_path(int tox, int toy, vector<vector<pii>>& from)
{
    vector<pii> path;
    int atx = tox, aty = toy;
    do
    {
        path.push_back({atx, aty});
        tie(atx, aty) = from[atx][aty];
    } while(make_pair(atx, aty) != make_pair(-1, -1));
    reverse(path.begin(), path.end());
    return path;
}

vector<pii> get_shortest_path(int fromx, int fromy, int tox, int toy, vector<vector<int>>& fixed)
{
    assert(is_valid(fromx, fromy) && is_valid(tox, toy) && !fixed[fromx][fromy] && !fixed[tox][toy]);
    vector<vector<int>> dist(n, vector<int>(n, 2e9));
    vector<vector<pii>> from(n, vector<pii>(n, {-1, -1}));
    
    calc_shortest_path(fromx, fromy, dist, from, fixed);
    return recover_path(tox, toy, from);
}

vector<pii> get_path_from_closest_occurance(int tox, int toy, int target_value, vector<vector<int>>& current_grid, vector<vector<int>>& fixed)
{
    assert(is_valid(tox, toy) && !fixed[tox][toy]);
    vector<vector<int>> dist(n, vector<int>(n, 2e9));
    vector<vector<pii>> from(n, vector<pii>(n, {-1, -1}));
    
    calc_shortest_path(tox, toy, dist, from, fixed);
    int fromx = -1, fromy = -1;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            if(current_grid[i][j] == target_value && ((fromx == -1 && fromy == -1) || dist[i][j] < dist[fromx][fromy]))
            {
                fromx = i;
                fromy = j;
            }
    assert(fromx != -1 && fromy != -1);
    vector<pii> result = recover_path(fromx, fromy, from);
    reverse(result.begin(), result.end());
    return result;
}

string apply_and_get_operation_string(vector<pii> path, vector<vector<int>>& current_grid)
{
    assert(!path.empty());
    int current_start_val = current_grid[path[0].first][path[0].second];
    string ops;
    for(int i = 1; i < path.size(); i++)
    {
        int movex = path[i].first - path[i - 1].first;
        int movey = path[i].second - path[i - 1].second;
        assert(movement_to_direction_character_map.count({movex, movey}));
        ops += movement_to_direction_character_map[{movex, movey}];
        current_grid[path[i - 1].first][path[i - 1].second] = current_grid[path[i].first][path[i].second];
    }
    current_grid[path.back().first][path.back().second] = current_start_val;
    return ops;
}

string move_cell(vector<pii> path, vector<vector<int>>& current_grid, vector<vector<int>>& fixed, int& empty_cell_x, int& empty_cell_y)
{
    // vector<pii> path = get_path_from_closest_occurance(tox, toy, target_value, current_grid, fixed);
    int tox = path.back().first, toy = path.back().second;
    int target_value = current_grid[path[0].first][path[0].second];
    assert(!path.empty());
    string ops;
    for(int i = 1; i < path.size(); i++)
    {
        // Protect the value we intend to move (currently at path[i - 1]), so we don't accidentally change its position while moving the empty cell.
        fixed[path[i - 1].first][path[i - 1].second] = 1;
        // Move empty cell to target cell (the adjacent cell we intended to move the value to)
        ops += apply_and_get_operation_string(get_shortest_path(empty_cell_x, empty_cell_y, path[i].first, path[i].second, fixed), current_grid);
        fixed[path[i - 1].first][path[i - 1].second] = 0;
        ops += apply_and_get_operation_string({path[i], path[i - 1]}, current_grid);
        tie(empty_cell_x, empty_cell_y) = path[i - 1];
    }
    assert(current_grid[tox][toy] == target_value);
    return ops;
}


string exact_slide_solver(vector<vector<int>>& current, vector<vector<int>>& target)
{
    int empty_cell_x = -1, empty_cell_y = -1;
    vector<int> mask_cnts(16);
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
        {
            mask_cnts[current[i][j]]++;
            if(current[i][j] == 0)
            {
                assert(empty_cell_x == -1 && empty_cell_y == -1);
                empty_cell_x = i;
                empty_cell_y = j;
            }
        }
    assert(empty_cell_x != -1 && empty_cell_y != -1);

    vector<vector<int>> fixed(n, vector<int>(n, 0));

    
    string ans;
    for(int i = n - 1; i > 2; i--)
    {
        // Fix last row
        for(int j = i; j > 1; j--)
        {
            ans += move_cell(get_path_from_closest_occurance(i, j, target[i][j], current, fixed), current, fixed, empty_cell_x, empty_cell_y);
            fixed[i][j] = 1;
        }
        // Handle first two columns of last row
        // Written this way to prevent issues with the first getting stuck, should be optimizable.
        ans += move_cell(get_path_from_closest_occurance(0, 0, target[i][0], current, fixed), current, fixed, empty_cell_x, empty_cell_y);
        fixed[0][0] = 1;
        ans += move_cell(get_path_from_closest_occurance(i, 0, target[i][1], current, fixed), current, fixed, empty_cell_x, empty_cell_y);
        fixed[0][0] = 0;
        fixed[i][0] = 1;
        ans += move_cell(get_shortest_path(0, 0, i - 1, 0, fixed), current, fixed, empty_cell_x, empty_cell_y);
        fixed[i - 1][0] = 1;
        ans += apply_and_get_operation_string(get_shortest_path(empty_cell_x, empty_cell_y, i, 1, fixed), current);
        fixed[i][0] = fixed[i - 1][0] = 0;
        empty_cell_x = i - 1;
        empty_cell_y = 0;
        ans += apply_and_get_operation_string({make_pair(i, 1), make_pair(i, 0), make_pair(i - 1, 0)}, current);
        fixed[i][0] = fixed[i][1] = 1;
        // Fix last col
        for(int j = i - 1; j > 1; j--)
        {
            ans += move_cell(get_path_from_closest_occurance(j, i, target[j][i], current, fixed), current, fixed, empty_cell_x, empty_cell_y);
            fixed[j][i] = 1;
        }
        // Handle first two rows of last column
        // Written this way to prevent issues with the first getting stuck, should be optimizable.
        ans += move_cell(get_path_from_closest_occurance(0, 0, target[0][i], current, fixed), current, fixed, empty_cell_x, empty_cell_y);
        fixed[0][0] = 1;
        ans += move_cell(get_path_from_closest_occurance(0, i, target[1][i], current, fixed), current, fixed, empty_cell_x, empty_cell_y);
        fixed[0][0] = 0;
        fixed[0][i] = 1;
        ans += move_cell(get_shortest_path(0, 0, 0, i - 1, fixed), current, fixed, empty_cell_x, empty_cell_y);
        fixed[0][i - 1] = 1;
        ans += apply_and_get_operation_string(get_shortest_path(empty_cell_x, empty_cell_y, 1, i, fixed), current);
        fixed[0][i] = fixed[0][i - 1] = 0;
        empty_cell_x = 0;
        empty_cell_y = i - 1;
        ans += apply_and_get_operation_string({make_pair(1, i), make_pair(0, i), make_pair(0, i - 1)}, current);
        fixed[0][i] = fixed[1][i] = 1;
    }
    // TODO: Figure out how to solve if the 3 cells of the 2x2 are rotationally opposite of what we need.
    return ans;
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> t;
    vector<int> mask_cnts(16);
    vector<vector<int>> grid_masks(n, vector<int>(n));
    for(int i = 0; i < n; i++)
    {
        string s;
        cin >> s;
        for(int j = 0; j < n; j++)
        {
            grid_masks[i][j] = (s[j] >= 'a' && s[j] <= 'z') ? (s[j] - 'a' + 10) : (s[j] - '0');
            mask_cnts[grid_masks[i][j]]++;
        }
    }
    vector<vector<int>> best_grid;
    int best_score = 0;
    auto grid_choose_start = chrono::high_resolution_clock::now();
    int times = 0;
    while(chrono::duration_cast<chrono::milliseconds>(chrono::high_resolution_clock::now() - grid_choose_start).count() < GRID_CHOOSE_TIMEOUT_MILLIS)
    {
        vector<vector<int>> cur_grid;
        int cur_score;
        tie(cur_grid, cur_score) = get_random_tree(mask_cnts);
        if(cur_score > best_score)
        {
            best_score = cur_score;
            best_grid = cur_grid;
        }
        times++;
    }
    assert(best_grid[0][0] == 0);
    for(auto row : best_grid)
        for(auto x : row)
            mask_cnts[x]--;
    for(int i = 0; i <= 15; i++)
        assert(mask_cnts[i] == 0);
    string ans = exact_slide_solver(grid_masks, best_grid);
    while(ans.size() > t)
        ans.pop_back();
    assert(ans.size() <= t);
    cout << ans << "\n";
    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘std::string apply_and_get_operation_string(std::vector<std::pair<int, int> >, std::vector<std::vector<int> >&)’:
./Main.cpp:220:22: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::pair<int, int> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  220 |     for(int i = 1; i < path.size(); i++)
      |                    ~~^~~~~~~~~~~~~
./Main.cpp: In function ‘std::string move_cell(std::vector<std::pair<int, int> >, std::vector<std::vector<int> >&, std::vector<std::vector<int> >&, int&, int&)’:
./Main.cpp:239:22: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::pair<int, int> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  239 |     for(int i = 1; i < path.size(); i++)
      |                    ~~^~~~~~~~~~~~~
./Main.cpp: In function ‘int32_t main()’:
./Main.cpp:364:22: warning: comparison of integer expressions of different signedness: ‘std::__cxx11::basic_string<char>::size_type’ {aka ‘long unsigned int’} and ‘int’ [-Wsign-compare]
  364 |     while(ans.size() > t)
      |           ~~~~~~~~~~~^~~
In file included from /usr/include/c++/9/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:33,
                 from ./Main.cpp:1:
./Main.cpp:366:23: warning: comparison of integer expressions of different signedness: ‘std::__cxx11::basic_string<char>::size_type’ {aka ‘long unsigned int’} and ‘int’ [-Wsign-compare]
  366 |     assert(ans.size() <= t);
      |            ~~~~~~~~~~~^~~~

Judge Result