kinho

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;

const int MAXV = 10000;
const int INF = 1e9;

const int dr[4] = { 0, 1, 0, -1 };
const int dc[4] = { 1, 0, -1, 0 };

int R, C, S;
vector<int> length;
vector<vector<bool>> isWormhole;
vector<pair<int, int>> wormholes;
vector<vector<int>> grid;
vector<vector<bool>> occupied;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void read_input(){
    cin >> C >> R >> S;

    length.resize(S);
    for(int i = 0; i < S; i++)
        cin >> length[i];

    cin.ignore();

    vector<string> input(R);
    grid.assign(R, vector<int>(C));
    isWormhole.assign(R, vector<bool>(C, false));
    occupied.assign(R, vector<bool>(C, false));

    for(int i = 0; i < R; i++) getline(cin, input[i]);

    for(int i = 0; i < R; i++){
        int cnt = 0;
        string number;
        stringstream ss(input[i]);
        while(ss >> number){
            if (number != "*") grid[i][cnt] = stoi(number);
            else grid[i][cnt] = 0, isWormhole[i][cnt] = true, wormholes.emplace_back(i, cnt);
            cnt++;
        }
    }
}

ll score(vector<ii> &snake){
    ll ret = 0;

    for(int i=0;i< (int) snake.size();i++){
        int x = snake[i].first;
        int y = snake[i].second;

        ret += ll(grid[x][y]);
    }

    return ret;
}

ii get_new_random_pos() {
    int row = uniform_int_distribution<int>(0, R - 1)(rng);
    int col = uniform_int_distribution<int>(0, C - 1)(rng);
    return make_pair(row, col);
}

bool valid(ii pos) {
    return !occupied[pos.first][pos.second];
}

ii get_new_random_wormhole() {
    int size = wormholes.size();
    return wormholes[uniform_int_distribution<int>(0, size - 1)(rng)];
}

void clear_path(vector<ii> &positions) {
    for (auto [row, col]: positions)
        occupied[row][col] = false;
}

vector<ii> get_new_random_path(int id) {
    const int max_attempts = 10;
    const double prob_choose = 0.9;

    if (uniform_real_distribution<double>(0, 1.0)(rng) > prob_choose)
        return vector<ii>();

    int attempts = 0;
    ii initial = get_new_random_pos();

    while ((!valid(initial) || isWormhole[initial.first][initial.second]) && attempts < max_attempts)
        initial = get_new_random_pos(), attempts++;

    if (!valid(initial) || isWormhole[initial.first][initial.second])
        return vector<ii>();

    ii curr = initial;
    vector<ii> positions(1, initial);
    occupied[curr.first][curr.second] = true;
    bool entry = false;

    for (int i = 1; i < length[id]; i++) {
        if (isWormhole[curr.first][curr.second] && entry) {
            if ((int) wormholes.size() == 1) {
                clear_path(positions);
                return vector<ii>();
            }

            ii newPos;
            do newPos = get_new_random_wormhole();
            while (newPos == curr);

            positions.push_back(newPos);
            curr = newPos;
            entry = false;
        } else {
            ii newPos;
            int dir, chosen = 0;

            do {
                dir = uniform_int_distribution<int>(0, 3)(rng);
                newPos = make_pair((curr.first + dr[dir] + R) % R, (curr.second + dc[dir] + C) % C);
                chosen |= (1 << dir);
            } while (!valid(newPos) && chosen != 15);

            if (!valid(newPos)) {
                clear_path(positions);
                return vector<ii>();
            }

            if (isWormhole[newPos.first][newPos.second]) entry = true;
            else occupied[newPos.first][newPos.second] = true;

            positions.push_back(newPos);
            curr = newPos;
        }
    }

    if (isWormhole[curr.first][curr.second]) {
        clear_path(positions);
        return vector<ii>();
    }

    return positions;
}

vector<vector<ii>> get_initial_paths() {
    vector<vector<ii>> paths;
    for (int i = 0; i < S; i++)
        paths.push_back(get_new_random_path(i));

    return paths;
}

void mark_snake_path(const vector<ii>& snake_path) {
    for(auto& [x, y] : snake_path) {
        if(isWormhole[x][y]) continue;
        occupied[x][y] = true;
    }
}

ll solution_score(const vector<vector<ii>>& S) {
    ll ret = 0;
    for(auto snake_path : S) {
        ret += score(snake_path);
    }
    return ret;
}

void undo_snake_path(const vector<ii>& snake_path) {
    for(auto& [x, y] : snake_path) {
        if(isWormhole[x][y]) continue;
        occupied[x][y] = false;
    }
}
tuple<int, vector<ii>> get_neighborhood(const vector<vector<ii>>& snakes) {
    int S = (int)snakes.size();
    int id = uniform_int_distribution<int>(0, S - 1)(rng);
    auto new_path = get_new_random_path(id);
    undo_snake_path(snakes[id]);
    undo_snake_path(new_path);
    return make_tuple(id, new_path);
}

map<pair<int, int>, char> direction;

void init_directions() {
  direction[{1, 0}] = 'D';
  direction[{0, 1}] = 'R';
  direction[{R - 1, 0}] = 'U';
  direction[{0, C - 1}] = 'L';
}

void print_solution(const vector<vector<ii>>& S) {
    cout << "#####################\n";
    for(const auto& snake_path : S) {
        if(snake_path.empty()) {
            cout << '\n';
            continue;
        }
        cout << snake_path[0].second << ' ' << snake_path[0].first << ' ';
        int len = (int)snake_path.size();
        for(int i = 1; i < len; ++i) {
            int dx = (snake_path[i].first - snake_path[i - 1].first + R) % R;
            int dy = (snake_path[i].second - snake_path[i - 1].second + C) % C;

            if (isWormhole[snake_path[i].first][snake_path[i].second]) {
                if (isWormhole[snake_path[i - 1].first][snake_path[i - 1].second]) {
                    cout << snake_path[i].second << " " << snake_path[i].first;
                    continue;
                }
            }

            cout << direction[{dx, dy}] << ' ';
        }
        cout << '\n';
    }
    cout << "#####################\n";
}

void sAnnealing(){
    // pseudo-code
    /************* setar isso aqui inicialmente
    S0 = estado inicial
    M = numero maximo de iteracoes
    P = pertubacoes por iteracao
    L = numero maximo de sucessos por iteracoes
    alpha = fator de reducao da temperatura
    ******************************************/
    double TEMP_INICIAL = 1000.0;
    double alpha = 0.995;
    int M = 10000;
    int P = 100;
    int print_per_iterations = M / 10;
    double barreira = 1e-8;

    vector<vector<ii>> S = get_initial_paths();
    ll total_score = solution_score(S);
    double T0 = TEMP_INICIAL;
    double T = T0;

    for(int i=0;i<=M;i++){
        for(int j=0;j<=P;j++){
            auto [snake_id, new_path] = get_neighborhood(S);

            ll delta = score(S[snake_id]) - score(new_path);

            // energia negativa -> melhor solucao
            if(delta <= 0.0 || exp(-delta/T) > uniform_real_distribution<double>(0, 1.0)(rng)){
                mark_snake_path(new_path);
                S[snake_id].swap(new_path);
                total_score -= delta;
            } else {
                mark_snake_path(S[snake_id]);
            }
        }
        T = T*alpha;
        if (T < barreira) {
            print_solution(S);
            break;
        }

        cerr << "----------------------------------------------------" << '\n';
        cerr << "total_score: " << total_score << '\n';
        cerr << "temperatura: " << T << '\n';
        cerr << "iteracoes: " << i << "/" << M << "\n";

        if (i % print_per_iterations == 0)
            print_solution(S);
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    read_input();
    init_directions();
    sAnnealing();
}