Submission #32167323

---

Source Code Expand

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

const int maxnsq = 105, GRID_CHOOSE_TIMEOUT_MILLIS = 1400, OVERALL_SAFETY_TIMEOUT_MILLIS = 2700;

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'}
};

class InvalidStateException : public exception
{
    string _msg;
  public:
    InvalidStateException(const string& msg) : _msg(msg) {}

    virtual const char* what() const noexcept override { return _msg.c_str(); }
}; 

class SlidingPuzzleSolverState
{
  public:
    int n, good = 0;
    string ans;
    vector<vector<int>> current, target, fixed;
    SlidingPuzzleSolverState(int _n, vector<vector<int>> _current, vector<vector<int>> _target) : 
        n(_n), 
        current(_current), 
        target (_target)
    {
        fixed.resize(n, vector<int>(n, 0));
    }
};

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;
}

template <typename T> T random_order(T original_list)
{
    shuffle(original_list.begin(), original_list.end(), rng);
    return original_list;
}

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 : random_order(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)
{
    assert(!path.empty());
    int tox = path.back().first, toy = path.back().second;
    int target_value = current_grid[path[0].first][path[0].second];
    assert(target_value != 0);  // Use apply_and_get_operation_string to move the empty cell, move_cell is only for non-empty cells.
    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)
        assert(current_grid[empty_cell_x][empty_cell_y] == 0);
        ops += apply_and_get_operation_string(get_shortest_path(empty_cell_x, empty_cell_y, path[i].first, path[i].second, fixed), current_grid);
        if(current_grid[path[i].first][path[i].second] != 0)
            throw InvalidStateException("Empty cell can't be moved to required position!");
        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[empty_cell_x][empty_cell_y] == 0);
    }
    assert(current_grid[tox][toy] == target_value);
    return ops;
}

string fix_row(int idx, vector<vector<int>>& current, vector<vector<int>>& target, vector<vector<int>>& fixed, int& empty_cell_x, int& empty_cell_y, int safe_mode)
{
    int move_back_value = (safe_mode) ? 0 : idx - 3;

    string ans;
    // Fix last row
    for(int j = idx; j > 1; j--)
        if(!fixed[idx][j])
        {
            ans += move_cell(get_path_from_closest_occurance(idx, j, target[idx][j], current, fixed), current, fixed, empty_cell_x, empty_cell_y);
            fixed[idx][j] = 1;
        }
    if(!fixed[idx][0] || !fixed[idx][1])
    {
        // Handle first two columns of last row
        // Written this way to prevent issues in some cases where the needed value gets stuck in the last row after the first move.
        ans += move_cell(get_path_from_closest_occurance(move_back_value, 0, target[idx][0], current, fixed), current, fixed, empty_cell_x, empty_cell_y);
        fixed[move_back_value][0] = 1;
        ans += move_cell(get_path_from_closest_occurance(idx, 0, target[idx][1], current, fixed), current, fixed, empty_cell_x, empty_cell_y);
        fixed[move_back_value][0] = 0;
        fixed[idx][0] = 1;
        ans += move_cell(get_shortest_path(move_back_value, 0, idx - 1, 0, fixed), current, fixed, empty_cell_x, empty_cell_y);
        fixed[idx - 1][0] = 1;
        ans += apply_and_get_operation_string(get_shortest_path(empty_cell_x, empty_cell_y, idx, 1, fixed), current);
        fixed[idx][0] = fixed[idx - 1][0] = 0;
        empty_cell_x = idx - 1;
        empty_cell_y = 0;
        ans += apply_and_get_operation_string({make_pair(idx, 1), make_pair(idx, 0), make_pair(idx - 1, 0)}, current);
        assert(current[idx][0] == target[idx][0] && current[idx][1] == target[idx][1]);
        fixed[idx][0] = fixed[idx][1] = 1;
    }
    return ans;
}

string fix_col(int idx, vector<vector<int>>& current, vector<vector<int>>& target, vector<vector<int>>& fixed, int& empty_cell_x, int& empty_cell_y, int safe_mode)
{
    int move_back_value = (safe_mode) ? 0 : idx - 3;

    string ans;
    // Fix last col
    for(int j = idx; j > 1; j--)
        if(!fixed[j][idx])
        {
            ans += move_cell(get_path_from_closest_occurance(j, idx, target[j][idx], current, fixed), current, fixed, empty_cell_x, empty_cell_y);
            fixed[j][idx] = 1;
        }
    if(!fixed[0][idx] || !fixed[1][idx])
    {
        // 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, move_back_value, target[0][idx], current, fixed), current, fixed, empty_cell_x, empty_cell_y);
        fixed[0][move_back_value] = 1;
        ans += move_cell(get_path_from_closest_occurance(0, idx, target[1][idx], current, fixed), current, fixed, empty_cell_x, empty_cell_y);
        fixed[0][move_back_value] = 0;
        fixed[0][idx] = 1;
        ans += move_cell(get_shortest_path(0, move_back_value, 0, idx - 1, fixed), current, fixed, empty_cell_x, empty_cell_y);
        fixed[0][idx - 1] = 1;
        ans += apply_and_get_operation_string(get_shortest_path(empty_cell_x, empty_cell_y, 1, idx, fixed), current);
        fixed[0][idx] = fixed[0][idx - 1] = 0;
        empty_cell_x = 0;
        empty_cell_y = idx - 1;
        ans += apply_and_get_operation_string({make_pair(1, idx), make_pair(0, idx), make_pair(0, idx - 1)}, current);
        assert(current[0][idx] == target[0][idx] && current[1][idx] == target[1][idx]);
        fixed[0][idx] = fixed[1][idx] = 1;
    }
    return ans;
}

int is_valid_3x3(int x, int y)
{
    return x >= 0 && x < 3 && y >= 0 && y < 3;
}

map<vector<vector<int>>, string> solve_3x3_op_strings;

void calculate_3x3_results()
{
    vector<vector<int>> basemask(3);
    for(int i = 0; i < 3; i++)
        for(int j = 0; j < 3; j++)
            basemask[i].push_back(3 * i + j);
    solve_3x3_op_strings[basemask] = "";
    queue<vector<vector<int>>> q;
    q.push(basemask);
    vector<vector<int>> curmask, nemask;
    while(!q.empty())
    {
        curmask = q.front();
        q.pop();
        for(int i = 0; i < 3; i++)
            for(int j = 0; j < 3; j++)
                if(curmask[i][j] == 0)
                    for(auto ne : dirs)
                    {
                        int nex = i + ne.first;
                        int ney = j + ne.second;
                        if(!is_valid_3x3(nex, ney))
                            continue;
                        nemask = curmask;
                        swap(nemask[i][j], nemask[nex][ney]);
                        if(!solve_3x3_op_strings.count(nemask))
                        {
                            assert(movement_to_direction_character_map.count({-ne.first, -ne.second}));
                            solve_3x3_op_strings[nemask] = solve_3x3_op_strings[curmask] + movement_to_direction_character_map[{-ne.first, -ne.second}];
                            q.push(nemask);
                        }
                    }
    }
}

string solve3x3(vector<vector<int>>& current, vector<vector<int>>& target, vector<vector<int>>& fixed)
{
    int req_rep_cnt[16] = {0};
    map<pii, int> req_pos;
    for(int i = 0; i < 3; i++)
        for(int j = 0; j < 3; j++)
        {
            req_pos[{target[i][j], req_rep_cnt[target[i][j]]}] = 3 * i + j;
            req_rep_cnt[target[i][j]]++;
        }
    // shuffle the duplicate matching order to ensure we don't repeatedly try the same bad reodering.
    vector<pii> order;
    for(int i = 0; i < 3; i++)
        for(int j = 0; j < 3; j++)
            order.push_back({i, j});
    shuffle(order.begin(), order.end(), rng);   
    int base_rep_cnt[16] = {0};
    vector<vector<int>> transformation(3, vector<int>(3));
    for(auto x : order)
    {
        int i = x.first, j = x.second;
        transformation[i][j] = req_pos[{current[i][j], base_rep_cnt[current[i][j]]}];
        base_rep_cnt[current[i][j]]++;
    }
    if(solve_3x3_op_strings.count(transformation))
    {
        string res = solve_3x3_op_strings[transformation];
        reverse(res.begin(), res.end());
        if(!res.empty())
            for(int i = 0; i < 3; i++)
                for(int j = 0; j < 3; j++)
                    current[i][j] = target[i][j];
        return res;
    }
    return "";
}

vector<SlidingPuzzleSolverState> exact_slide_solver(vector<SlidingPuzzleSolverState> checkpoints)
{
    assert(!checkpoints.empty());

    int empty_cell_x = -1, empty_cell_y = -1;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            if(checkpoints.back().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);

    std::vector<string (*)(int, vector<vector<int>>&, vector<vector<int>>&, vector<vector<int>>&, int&, int&, int)> rearrangable_handlers = {
        fix_row,
        fix_col
    };
        
    string ans;
    for(int i = n - (int)(checkpoints.size()); i > 2; i--)
    {
        SlidingPuzzleSolverState curstate = checkpoints.back();
        if(uniform_int_distribution<int>(0, 1)(rng))
            shuffle(rearrangable_handlers.begin(), rearrangable_handlers.end(), rng);

        // So I have a heuristic which can get stuck at times, but 
        // works better most of the time. So lets try to use it when 
        // possible, if it fails we'll fall back to the safe version 
        // as needed.
        vector<vector<int>> current_copy, target_copy, fixed_copy;
        int empty_cell_x_copy, empty_cell_y_copy;


        for(auto handler_func : rearrangable_handlers)
        {
            current_copy = curstate.current;
            target_copy = curstate.target;
            fixed_copy = curstate.fixed;
            empty_cell_x_copy = empty_cell_x;
            empty_cell_y_copy = empty_cell_y;

            string curans;
            try 
            {
                curans = handler_func(i, curstate.current, curstate.target, curstate.fixed, empty_cell_x, empty_cell_y, 0);
            } 
            catch(InvalidStateException e)
            {
                curstate.current = current_copy;
                curstate.target = target_copy;
                curstate.fixed = fixed_copy;
                empty_cell_x = empty_cell_x_copy;
                empty_cell_y = empty_cell_y_copy;
                curans = handler_func(i, curstate.current, curstate.target, curstate.fixed, empty_cell_x, empty_cell_y, 1);
            }
            curstate.ans += curans;
        }
        checkpoints.push_back(curstate);
    }

    // Solve 3x3
    SlidingPuzzleSolverState curstate = checkpoints.back();
    curstate.ans += solve3x3(curstate.current, curstate.target, curstate.fixed);
    checkpoints.push_back(curstate);
    checkpoints.back().good = 1;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            checkpoints.back().good &= (checkpoints.back().current[i][j] == checkpoints.back().target[i][j]);
    return checkpoints;
}

// Consider the set of values {lo, lo + 1, ..., hi}.
// The probability of picking the i-th largest value in this set is 1 / (i + 1).
int get_weighted_random(int lo, int hi, int factor)
{
    assert(lo <= hi && factor >= 1);
    int res = lo;
    for(int i = 0; i < factor; i++)
        res = max(res, uniform_int_distribution<int>(lo, hi)(rng));
    return res;
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    auto overall_start = chrono::high_resolution_clock::now();
    calculate_3x3_results();
    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(best_score < n * n - 1 &&
        chrono::duration_cast<chrono::milliseconds>(chrono::high_resolution_clock::now() - grid_choose_start).count() < GRID_CHOOSE_TIMEOUT_MILLIS &&
        chrono::duration_cast<chrono::milliseconds>(chrono::high_resolution_clock::now() - overall_start).count() < OVERALL_SAFETY_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++;
    }
    cerr << "GENERATED " << times << " GRIDS\n";
    cerr << "Best grid has a tree of size " << best_score << " (" << (n * n - 1 - best_score) << " less than optimal)\n";

    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);
    vector<SlidingPuzzleSolverState> best_checkpoints;
    SlidingPuzzleSolverState starting_state(n, grid_masks, best_grid);
    best_checkpoints.push_back(starting_state);
    int attempts = 0;
    while(chrono::duration_cast<chrono::milliseconds>(chrono::high_resolution_clock::now() - overall_start).count() < OVERALL_SAFETY_TIMEOUT_MILLIS)
    {
        assert(!best_checkpoints.empty());
        int take_lo = 1, take_hi = best_checkpoints.size();
        if(take_hi > 1)
            take_hi--;
        int take_actual = get_weighted_random(take_lo, take_hi, take_hi);
        vector<SlidingPuzzleSolverState> new_checkpoints = exact_slide_solver({best_checkpoints.begin(), best_checkpoints.begin() + take_actual});
        assert(new_checkpoints.size() + 1 == n);
        if(attempts == 0 || new_checkpoints.back().good > best_checkpoints.back().good || ((new_checkpoints.back().good == best_checkpoints.back().good) && new_checkpoints.back().ans.size() < best_checkpoints.back().ans.size()))
            best_checkpoints = new_checkpoints;
        attempts++;
    }
    cerr << best_checkpoints.back().ans.size() << "\t" << best_checkpoints.back().good << "\t" << attempts << "\n";
    while(best_checkpoints.back().ans.size() > t)
        best_checkpoints.back().ans.pop_back();
    assert(best_checkpoints.back().ans.size() <= t);
    cout << best_checkpoints.back().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:249: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]
  249 |     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:268: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]
  268 |     for(int i = 1; i < path.size(); i++)
      |                    ~~^~~~~~~~~~~~~
./Main.cpp: In function ‘std::string solve3x3(std::vector<std::vector<int> >&, std::vector<std::vector<int> >&, std::vector<std::vector<int> >&)’:
./Main.cpp:396:97: warning: unused parameter ‘fixed’ [-Wunused-parameter]
  396 | string solve3x3(vector<vector<int>>& current, vector<vector<int>>& target, vector<vector<int>>& fixed)
      |                                                                            ~~~~~~~~~~~~~~~~~~~~~^~~~~
./Main.cpp: In function ‘std::vector<SlidingPuzzleSolverState> exact_slide_solver(std::vector<SlidingPuzzleSolverState>)’:
./Main.cpp:481:41: warning: catching polymorphic type ‘class InvalidStateException’ by value [-Wcatch-value=]
  481 |             catch(InvalidStateException e)
      |                                         ^
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: In function ‘int32_t main()’:
./Main.cpp:575:43: warning: comparison of integer expressions of different signedness: ‘std::vector<SlidingPuzzleSolverState>::size_type’ {aka ‘long ...

Judge Result