Submission #72329805

---

Source Code Expand

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <climits>

using namespace std;

const int N = 20;
const int MAX_DEPTH = 6; 
const int SEARCH_WIDTH = 8;

struct Point {
    int r, c;
    bool operator==(const Point& other) const {
        return r == other.r && c == other.c;
    }
    bool operator!=(const Point& other) const {
        return !(*this == other);
    }
};

struct CardPos {
    int id;
    Point p[2];
    bool removed;
};

struct MoveStep {
    int card_id;
    int point_idx;
};

Point current_pos = {0, 0};
int remaining_pairs;
vector<CardPos> cards;

int dist(Point a, Point b) {
    return abs(a.r - b.r) + abs(a.c - b.c);
}

string get_move_path(Point from, Point to) {
    string path = "";
    if (to.r > from.r) path += string(to.r - from.r, 'D');
    else path += string(from.r - to.r, 'U');
    if (to.c > from.c) path += string(to.c - from.c, 'R');
    else path += string(from.c - to.c, 'L');
    return path;
}

void execute_move(Point dest, bool pick) {
    string path = get_move_path(current_pos, dest);
    for (char c : path) cout << c << "\n";
    if (pick) {
        cout << "Z\n";
    }
    current_pos = dest;
}

double best_cost_per_pair;
vector<MoveStep> best_sequence;

void dfs(Point curr, vector<MoveStep>& current_path, int current_dist, vector<bool>& visited_card_id) {
    int depth = current_path.size();
    
    if (depth > 0) {
        int return_dist = 0;
        Point last_pos = curr;
        
        for (int i = depth - 1; i >= 0; --i) {
            int id = current_path[i].card_id;
            int picked_idx = current_path[i].point_idx;
            int other_idx = 1 - picked_idx;
            Point target = cards[id].p[other_idx];
            
            return_dist += dist(last_pos, target);
            last_pos = target;
        }
        
        int total_dist = current_dist + return_dist;
        double cost_per = (double)total_dist / depth;
        
        if (cost_per < best_cost_per_pair) {
            best_cost_per_pair = cost_per;
            best_sequence = current_path;
        }
    }

    if (depth >= MAX_DEPTH) return;

    struct Candidate {
        int id;
        int idx;
        int d;
    };
    vector<Candidate> candidates;
    candidates.reserve(remaining_pairs * 2);

    int max_val = cards.size();
    for(int i=0; i<max_val; ++i) {
        if(cards[i].removed || visited_card_id[i]) continue;
        
        int d0 = dist(curr, cards[i].p[0]);
        int d1 = dist(curr, cards[i].p[1]);
        
        candidates.push_back({i, 0, d0});
        candidates.push_back({i, 1, d1});
    }

    int limit = min((int)candidates.size(), SEARCH_WIDTH);
    partial_sort(candidates.begin(), candidates.begin() + limit, candidates.end(), 
        [](const Candidate& a, const Candidate& b){
            return a.d < b.d;
        });

    for(int i=0; i<limit; ++i) {
        if (visited_card_id[candidates[i].id]) continue;

        visited_card_id[candidates[i].id] = true;
        current_path.push_back({candidates[i].id, candidates[i].idx});
        
        dfs(cards[candidates[i].id].p[candidates[i].idx], 
            current_path, 
            current_dist + candidates[i].d, 
            visited_card_id);
            
        current_path.pop_back();
        visited_card_id[candidates[i].id] = false;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n_in;
    if (!(cin >> n_in)) return 0;

    int max_val = (N * N) / 2;
    cards.resize(max_val);
    for(int i=0; i<max_val; ++i) {
        cards[i].id = i;
        cards[i].p[0] = {-1, -1};
        cards[i].p[1] = {-1, -1};
        cards[i].removed = false;
    }
    remaining_pairs = max_val;

    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            int val;
            cin >> val;
            if (cards[val].p[0].r == -1) {
                cards[val].p[0] = {i, j};
            } else {
                cards[val].p[1] = {i, j};
            }
        }
    }

    vector<bool> visited_card_id(max_val, false);

    while (remaining_pairs > 0) {
        best_cost_per_pair = 1e18;
        best_sequence.clear();
        
        vector<MoveStep> current_path;
        current_path.reserve(MAX_DEPTH);
        
        dfs(current_pos, current_path, 0, visited_card_id);

        if (best_sequence.empty()) {
            int best_dist = 1e9;
            int target_id = -1;
            int target_idx = -1;
            
            for(int i=0; i<max_val; ++i) {
                if(cards[i].removed) continue;
                for(int k=0; k<2; ++k) {
                    int d = dist(current_pos, cards[i].p[k]);
                    if(d < best_dist) {
                        best_dist = d;
                        target_id = i;
                        target_idx = k;
                    }
                }
            }
            if(target_id != -1) {
                best_sequence.push_back({target_id, target_idx});
            } else {
                break;
            }
        }

        for (const auto& step : best_sequence) {
            execute_move(cards[step.card_id].p[step.point_idx], true);
        }

        for (int i = best_sequence.size() - 1; i >= 0; --i) {
            int id = best_sequence[i].card_id;
            int visited_idx = best_sequence[i].point_idx;
            int target_idx = 1 - visited_idx;
            
            execute_move(cards[id].p[target_idx], true);
            
            cards[id].removed = true;
        }
        
        remaining_pairs -= best_sequence.size();
    }

    return 0;
}

Submission Info

Judge Result