Submission #27966152

---

Source Code Expand

use grid::Coordinate;
#[allow(unused_imports)]
use proconio::*;
#[allow(unused_imports)]
use rand::prelude::*;
use std::{collections::VecDeque, time::Instant};

#[allow(unused_macros)]
macro_rules! chmin {
    ($base:expr, $($cmps:expr),+ $(,)*) => {{
        let cmp_min = min!($($cmps),+);
        if $base > cmp_min {
            $base = cmp_min;
            true
        } else {
            false
        }
    }};
}

#[allow(unused_macros)]
macro_rules! chmax {
    ($base:expr, $($cmps:expr),+ $(,)*) => {{
        let cmp_max = max!($($cmps),+);
        if $base < cmp_max {
            $base = cmp_max;
            true
        } else {
            false
        }
    }};
}

#[allow(unused_macros)]
macro_rules! min {
    ($a:expr $(,)*) => {{
        $a
    }};
    ($a:expr, $b:expr $(,)*) => {{
        std::cmp::min($a, $b)
    }};
    ($a:expr, $($rest:expr),+ $(,)*) => {{
        std::cmp::min($a, min!($($rest),+))
    }};
}

#[allow(unused_macros)]
macro_rules! max {
    ($a:expr $(,)*) => {{
        $a
    }};
    ($a:expr, $b:expr $(,)*) => {{
        std::cmp::max($a, $b)
    }};
    ($a:expr, $($rest:expr),+ $(,)*) => {{
        std::cmp::max($a, max!($($rest),+))
    }};
}

#[allow(unused_macros)]
macro_rules! mat {
    ($e:expr; $d:expr) => { vec![$e; $d] };
    ($e:expr; $d:expr $(; $ds:expr)+) => { vec![mat![$e $(; $ds)*]; $d] };
}

const N: usize = 20;
const MAX_TURN: usize = 5000;
const TL: f64 = 1.9;
const CANDIDATE_COUNT: usize = 10;
const MAX_INIT_REP: usize = 5;
const U: usize = 0;
const R: usize = 1;
const D: usize = 2;
const L: usize = 3;

#[derive(Debug, Clone)]
struct Input {
    n: usize,
    start: Coordinate,
    graph: Vec<Vec<[Option<Coordinate>; 4]>>,
    since: Instant,
}

impl Input {
    fn new(start: Coordinate, graph: Vec<Vec<[Option<Coordinate>; 4]>>) -> Self {
        let since = Instant::now();
        Self {
            n: N,
            start,
            graph,
            since,
        }
    }
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
#[allow(non_camel_case_types)]
enum Command {
    L,
    R,
    l,
    r,
    F,
}

impl ToString for Command {
    fn to_string(&self) -> String {
        match self {
            Command::L => String::from("L"),
            Command::R => String::from("R"),
            Command::l => String::from("l"),
            Command::r => String::from("r"),
            Command::F => String::from("F"),
        }
    }
}

enum Operation {
    Single(usize, Command),
    Multiple(usize, Vec<Operation>),
}

impl Operation {
    fn apply(
        &self,
        input: &Input,
        mut coordinate: Coordinate,
        mut direction: usize,
        mut cleaned: Vec<Vec<bool>>,
        mut turn: usize,
    ) -> (Coordinate, usize, Vec<Vec<bool>>, usize) {
        match self {
            Operation::Single(rep, command) => {
                for _ in 0..*rep {
                    if turn >= MAX_TURN {
                        break;
                    }

                    let edges = &input.graph[coordinate.row][coordinate.col];

                    match command {
                        Command::L => direction = direction.wrapping_sub(1) % 4,
                        Command::R => direction = (direction + 1) % 4,
                        Command::l => {
                            if edges[direction] == None {
                                direction = direction.wrapping_sub(1) % 4;
                            }
                        }
                        Command::r => {
                            if edges[direction] == None {
                                direction = (direction + 1) % 4;
                            }
                        }
                        Command::F => {
                            if let Some(next) = edges[direction] {
                                coordinate = next;
                                cleaned[next.row][next.col] = true;
                            }
                        }
                    }

                    turn += 1;
                }
            }
            Operation::Multiple(rep, operation) => {
                for _ in 0..*rep {
                    if turn >= MAX_TURN {
                        break;
                    }

                    for op in operation.iter() {
                        if turn >= MAX_TURN {
                            break;
                        }

                        let (c, d, cl, t) = op.apply(input, coordinate, direction, cleaned, turn);
                        coordinate = c;
                        direction = d;
                        cleaned = cl;
                        turn = t;
                    }
                }
            }
        }

        (coordinate, direction, cleaned, turn)
    }
}

impl ToString for Operation {
    fn to_string(&self) -> String {
        match self {
            Operation::Single(rep, command) => {
                let mut str = String::new();

                if *rep > 1 {
                    for c in rep.to_string().chars() {
                        str.push(c);
                    }
                }

                for c in command.to_string().chars() {
                    str.push(c);
                }

                str
            }
            Operation::Multiple(rep, operation) => {
                let mut str = String::new();

                if *rep > 1 {
                    for c in rep.to_string().chars() {
                        str.push(c);
                    }

                    str.push('(');
                }

                for op in operation.iter() {
                    for c in op.to_string().chars() {
                        str.push(c);
                    }
                }

                if *rep > 1 {
                    str.push(')');
                }

                str
            }
        }
    }
}

fn main() {
    let input = read_input();
    let operation = solve(&input);
    println!("{}", operation.to_string());
    eprintln!("{}", calc_score(&input, &operation));
}

fn read_input() -> Input {
    input! {
        s_row: usize,
        s_col: usize,
    }

    let start = Coordinate::new(s_row, s_col);

    let mut graph = mat![[None; 4]; N; N];

    for row in 0..N {
        input! {
            s: String
        }

        for (col, c) in s.chars().enumerate() {
            if c == '0' {
                graph[row][col][R] = Some(Coordinate::new(row, col + 1));
                graph[row][col + 1][L] = Some(Coordinate::new(row, col));
            }
        }
    }

    for row in 0..(N - 1) {
        input! {
            s: String
        }

        for (col, c) in s.chars().enumerate() {
            if c == '0' {
                graph[row][col][D] = Some(Coordinate::new(row + 1, col));
                graph[row + 1][col][U] = Some(Coordinate::new(row, col));
            }
        }
    }

    let input = Input::new(start, graph);
    input
}

fn solve(input: &Input) -> Operation {
    let distances = calc_dists(input);
    let actual_distances = calc_actual_dists(input);
    let init_operation_candidates =
        get_init_operation_candidates(input, &distances, &actual_distances);

    let remainining_time = TL - (Instant::now() - input.since).as_secs_f64();
    let each_duration = remainining_time / init_operation_candidates.len() as f64;

    let mut best_score = std::i32::MAX;
    let mut best_init_operation = Operation::Single(1, Command::F);
    let mut best_tsp_perm = vec![];

    for init_operation in init_operation_candidates {
        let (init_coordinate, init_direction, cleaned) = generate_init_state(input);
        let (init_coordinate, init_direction, cleaned, _) =
            init_operation.apply(input, init_coordinate, init_direction, cleaned, 0);

        let unvisited = get_unvisited(&cleaned);

        if unvisited.len() == 0 {
            return init_operation;
        }

        let (tsp_perm, score) = tsp_annealing(
            init_coordinate,
            init_direction,
            &unvisited,
            &distances,
            &actual_distances,
            each_duration,
        );

        if chmin!(best_score, score) {
            best_init_operation = init_operation;
            best_tsp_perm = tsp_perm;
        }
    }

    let (init_coordinate, init_direction, cleaned) = generate_init_state(input);
    let (init_coordinate, init_direction, cleaned, _) =
        best_init_operation.apply(input, init_coordinate, init_direction, cleaned, 0);
    let unvisited = get_unvisited(&cleaned);

    let after_operation = get_operation(
        input,
        init_coordinate,
        init_direction,
        0,
        &unvisited,
        &best_tsp_perm,
    );

    Operation::Multiple(1, vec![best_init_operation, after_operation])
}

fn get_init_operation_candidates(
    input: &Input,
    distances: &[Vec<i32>],
    actual_distances: &[Vec<i32>],
) -> Vec<Operation> {
    let mut candidates = vec![];

    for operation in generate_init_candidates() {
        let score = estimate_score(input, &operation, distances, actual_distances);
        candidates.push((score, operation));
    }

    candidates.sort_by(|a, b| b.0.cmp(&a.0));

    while candidates.len() > CANDIDATE_COUNT {
        candidates.pop();
    }

    candidates.drain(..).map(|(_, op)| op).collect()
}

fn estimate_score(
    input: &Input,
    init_operation: &Operation,
    distances: &[Vec<i32>],
    actual_distances: &[Vec<i32>],
) -> i32 {
    let (init_coordinate, init_direction, cleaned) = generate_init_state(input);
    let (mut coordinate, mut direction, cleaned, _) =
        init_operation.apply(input, init_coordinate, init_direction, cleaned, 0);
    let unvisited = get_unvisited(&cleaned);

    if unvisited.len() == 0 {
        return calc_score(input, init_operation);
    }

    let (tsp_perm, _) = tsp_nn(
        coordinate,
        direction,
        &unvisited,
        &distances,
        &actual_distances,
    );
    let mut after_length = 0;
    let mut actual_length = 0;

    match init_operation {
        Operation::Single(_, _) => unreachable!(),
        Operation::Multiple(rep, ops) => {
            for op in ops.iter() {
                match op {
                    Operation::Single(_, _) => unreachable!(),
                    Operation::Multiple(rep, op) => actual_length += (rep * op.len()) as i32,
                }
            }
            actual_length *= *rep as i32;
        }
    }

    let mut flag = 0;

    for &(next_index, next_direction, next_flag) in tsp_perm.iter() {
        let next_coordinate = unvisited[next_index];
        let from = to_index(coordinate.row, coordinate.col, direction, flag);
        let to = to_index(
            next_coordinate.row,
            next_coordinate.col,
            next_direction,
            next_flag,
        );

        after_length += distances[from][to];
        actual_length += actual_distances[from][to];
        coordinate = next_coordinate;
        direction = next_direction;
        flag = next_flag;
    }

    // なんかおかしい
    if actual_length + 5 <= MAX_TURN as i32 {
        return -(init_operation.to_string().len() as i32 + after_length);
    } else {
        return std::i32::MIN;
    }
}

fn generate_init_state(input: &Input) -> (Coordinate, usize, Vec<Vec<bool>>) {
    let coordinate = input.start;
    let direction = U;
    let mut cleaned = mat![false; N; N];
    cleaned[coordinate.row][coordinate.col] = true;
    (coordinate, direction, cleaned)
}

fn generate_init_candidates() -> Vec<Operation> {
    let mut candidates = vec![];
    let init_turns = vec![
        4750, 4760, 4770, 4780, 4790, 4800, 4810, 4820, 4830, 4840, 4850, 4860, 4870, 4880, 4890,
        4900, 4910, 4920, 4930,
    ];

    for init_turn in init_turns {
        for left in 1..=MAX_INIT_REP {
            for right in 1..=MAX_INIT_REP {
                let rep = init_turn / (4 * (left + right));
                let operation = Operation::Multiple(
                    rep,
                    vec![
                        Operation::Multiple(
                            left,
                            vec![
                                Operation::Single(1, Command::L),
                                Operation::Single(1, Command::r),
                                Operation::Single(1, Command::r),
                                Operation::Single(1, Command::F),
                            ],
                        ),
                        Operation::Multiple(
                            right,
                            vec![
                                Operation::Single(1, Command::R),
                                Operation::Single(1, Command::l),
                                Operation::Single(1, Command::l),
                                Operation::Single(1, Command::F),
                            ],
                        ),
                    ],
                );
                candidates.push(operation);
                let operation = Operation::Multiple(
                    rep,
                    vec![
                        Operation::Multiple(
                            right,
                            vec![
                                Operation::Single(1, Command::R),
                                Operation::Single(1, Command::l),
                                Operation::Single(1, Command::l),
                                Operation::Single(1, Command::F),
                            ],
                        ),
                        Operation::Multiple(
                            left,
                            vec![
                                Operation::Single(1, Command::L),
                                Operation::Single(1, Command::r),
                                Operation::Single(1, Command::r),
                                Operation::Single(1, Command::F),
                            ],
                        ),
                    ],
                );
                candidates.push(operation);
            }
        }
    }

    candidates
}

fn calc_dists(input: &Input) -> Vec<Vec<i32>> {
    const LENGTH: usize = N * N * 4 * 3;
    let mut distances = mat![0; LENGTH; LENGTH];

    for row in 0..N {
        for col in 0..N {
            let coordinate = Coordinate::new(row, col);
            for dir in 0..4 {
                for flag in 0..3 {
                    let index = to_index(row, col, dir, flag);
                    let distances = &mut distances[index];
                    let dists = calc_dist(input, coordinate, dir, flag);

                    let mut index = 0;

                    for row in 0..N {
                        for col in 0..N {
                            for dir in 0..4 {
                                for flag in 0..3 {
                                    distances[index] = dists[row][col][dir][flag];
                                    index += 1;
                                }
                            }
                        }
                    }
                }
            }
        }
    }

    distances
}

fn calc_dist(
    input: &Input,
    start_coordinate: Coordinate,
    start_direction: usize,
    flag: usize,
) -> Vec<Vec<[[i32; 3]; 4]>> {
    let mut distances = mat![[[100000000; 3]; 4]; N; N];
    let mut queue = VecDeque::new();
    distances[start_coordinate.row][start_coordinate.col][start_direction][flag] = 0;
    queue.push_back((
        start_coordinate.row,
        start_coordinate.col,
        start_direction,
        flag,
    ));

    while let Some((row, col, dir, flag)) = queue.pop_front() {
        let dist = distances[row][col][dir][flag];

        // Forward
        if let Some(next) = input.graph[row][col][dir] {
            // 9 -> 10の時は考慮できないけどええやろ
            if flag == 2 {
                if chmin!(distances[next.row][next.col][dir][flag], dist) {
                    queue.push_front((next.row, next.col, dir, flag));
                }
            } else if flag < 2 {
                if chmin!(distances[next.row][next.col][dir][flag + 1], dist + 1) {
                    queue.push_back((next.row, next.col, dir, flag + 1));
                }
            }
        }

        // Left
        let next_dir = dir.wrapping_sub(1) % 4;
        if chmin!(distances[row][col][next_dir][0], dist + 1) {
            queue.push_back((row, col, next_dir, 0));
        }

        // Right
        let next_dir = (dir + 1) % 4;
        if chmin!(distances[row][col][next_dir][0], dist + 1) {
            queue.push_back((row, col, next_dir, 0));
        }
    }

    distances
}

fn calc_actual_dists(input: &Input) -> Vec<Vec<i32>> {
    const LENGTH: usize = N * N * 4 * 3;
    let mut distances = mat![0; LENGTH; LENGTH];

    for row in 0..N {
        for col in 0..N {
            let coordinate = Coordinate::new(row, col);
            for dir in 0..4 {
                for flag in 0..3 {
                    let index = to_index(row, col, dir, flag);
                    let distances = &mut distances[index];
                    let dists = calc_actual_dist(input, coordinate, dir, flag);

                    let mut index = 0;

                    for row in 0..N {
                        for col in 0..N {
                            for dir in 0..4 {
                                for flag in 0..3 {
                                    distances[index] = dists[row][col][dir][flag];
                                    index += 1;
                                }
                            }
                        }
                    }
                }
            }
        }
    }

    distances
}

fn calc_actual_dist(
    input: &Input,
    start_coordinate: Coordinate,
    start_direction: usize,
    flag: usize,
) -> Vec<Vec<[[i32; 3]; 4]>> {
    let mut distances = mat![[[100000000; 3]; 4]; N; N];
    let mut queue = VecDeque::new();
    distances[start_coordinate.row][start_coordinate.col][start_direction][flag] = 0;
    queue.push_back((
        start_coordinate.row,
        start_coordinate.col,
        start_direction,
        flag,
    ));

    while let Some((row, col, dir, flag)) = queue.pop_front() {
        let dist = distances[row][col][dir][flag];

        // Forward
        if let Some(next) = input.graph[row][col][dir] {
            let next_flag = (flag + 1).min(2);
            if chmin!(distances[next.row][next.col][dir][next_flag], dist + 1) {
                queue.push_back((next.row, next.col, dir, next_flag));
            }
        }

        // Left
        let next_dir = dir.wrapping_sub(1) % 4;
        if chmin!(distances[row][col][next_dir][0], dist + 1) {
            queue.push_back((row, col, next_dir, 0));
        }

        // Right
        let next_dir = (dir + 1) % 4;
        if chmin!(distances[row][col][next_dir][0], dist + 1) {
            queue.push_back((row, col, next_dir, 0));
        }
    }

    distances
}

fn get_unvisited(cleaned: &[Vec<bool>]) -> Vec<Coordinate> {
    let mut unvisited = vec![];

    for row in 0..N {
        for col in 0..N {
            if !cleaned[row][col] {
                unvisited.push(Coordinate::new(row, col));
            }
        }
    }

    unvisited
}

fn tsp_nn(
    mut coordinate: Coordinate,
    mut direction: usize,
    to_visits: &[Coordinate],
    distances: &[Vec<i32>],
    actual_distances: &[Vec<i32>],
) -> (Vec<(usize, usize, usize)>, i32) {
    let mut visited = vec![false; to_visits.len()];
    let mut flag = 0;
    let mut results = Vec::with_capacity(to_visits.len());
    let mut dist = 0;

    // とりあえずNearest Neighbor
    for _ in 0..visited.len() {
        let dists = &distances[to_index(coordinate.row, coordinate.col, direction, flag)];
        let dists_act =
            &actual_distances[to_index(coordinate.row, coordinate.col, direction, flag)];
        let mut best_dist = std::i32::MAX;
        let mut best_actual_dist = std::i32::MAX;
        let mut best_index = 0;
        let mut best_dir = 0;
        let mut best_flag = 0;

        for (i, next) in to_visits.iter().enumerate() {
            if visited[i] {
                continue;
            }

            for dir in 0..4 {
                for fl in 0..3 {
                    let d = dists[to_index(next.row, next.col, dir, fl)];
                    let d_act = dists_act[to_index(next.row, next.col, dir, fl)];

                    if chmin!(best_dist, d) {
                        best_actual_dist = d_act;
                        best_index = i;
                        best_dir = dir;
                        best_flag = fl;
                    } else if best_dist == d && chmin!(best_actual_dist, d_act) {
                        best_index = i;
                        best_dir = dir;
                        best_flag = fl;
                    } else if best_dist == d && best_actual_dist == d_act && chmax!(best_flag, fl) {
                        best_index = i;
                        best_dir = dir;
                    }
                }
            }
        }

        results.push((best_index, best_dir, best_flag));
        coordinate = to_visits[best_index];
        direction = best_dir;
        flag = best_flag;
        visited[best_index] = true;
        dist += best_dist;
    }

    (results, dist)
}

fn tsp_annealing(
    init_coordinate: Coordinate,
    init_direction: usize,
    to_visits: &[Coordinate],
    distances: &[Vec<i32>],
    actual_distances: &[Vec<i32>],
    duration: f64,
) -> (Vec<(usize, usize, usize)>, i32) {
    let (init_solution, init_score) = tsp_nn(
        init_coordinate,
        init_direction,
        to_visits,
        distances,
        actual_distances,
    );

    if init_solution.len() <= 2 {
        return (init_solution, init_score);
    }

    let mut solution = init_solution.clone();
    let mut best_solution = solution.clone();
    let mut current_score = init_score;
    let mut best_score = current_score;

    let since = Instant::now();
    let duration_inv = 1.0 / duration;

    let mut all_iter = 0;
    let mut valid_iter = 0;
    let mut accepted_count = 0;
    let mut update_count = 0;
    let mut rng = rand_pcg::Pcg64Mcg::new(42);

    let temp0 = 5e0;
    let temp1 = 1e-1;

    while (Instant::now() - since).as_secs_f64() < duration {
        all_iter += 1;
        let time = (std::time::Instant::now() - since).as_secs_f64() * duration_inv;
        let temp = f64::powf(temp0, 1.0 - time) * f64::powf(temp1, time);

        // 変形
        let mut new_perm = solution
            .iter()
            .map(|&(index, _, _)| index)
            .collect::<Vec<_>>();
        let left = rng.gen_range(0, new_perm.len() - 1);
        let right = rng.gen_range(left + 2, new_perm.len() + 1);

        new_perm[left..right].reverse();

        let mut coordinate = init_coordinate;
        let mut direction = init_direction;
        let mut flag = 0;
        let mut new_solution = Vec::with_capacity(solution.len());
        let mut new_score = 0;

        for &index in new_perm.iter() {
            let dists = &distances[to_index(coordinate.row, coordinate.col, direction, flag)];
            let dists_act =
                &actual_distances[to_index(coordinate.row, coordinate.col, direction, flag)];
            let mut best_dist = std::i32::MAX;
            let mut best_actual_dist = std::i32::MAX;
            let mut best_dir = 0;
            let mut best_flag = 0;
            let next = to_visits[index];

            for dir in 0..4 {
                for fl in 0..3 {
                    let d = dists[to_index(next.row, next.col, dir, fl)];
                    let d_act = dists_act[to_index(next.row, next.col, dir, fl)];

                    if chmin!(best_dist, d) {
                        best_actual_dist = d_act;
                        best_dir = dir;
                        best_flag = fl;
                    } else if best_dist == d && chmin!(best_actual_dist, d_act) {
                        best_dir = dir;
                        best_flag = fl;
                    } else if best_dist == d && best_actual_dist == d_act && chmax!(best_flag, fl) {
                        best_dir = dir;
                    }
                }
            }

            new_score += best_dist;
            new_solution.push((index, best_dir, best_flag));
            coordinate = next;
            direction = best_dir;
            flag = best_flag;
        }

        // スコア計算
        let score_diff = new_score - current_score;

        if score_diff <= 0 || rng.gen_bool(f64::exp(-score_diff as f64 / temp)) {
            // 解の更新
            current_score = new_score;
            solution = new_solution;
            accepted_count += 1;

            if chmin!(best_score, new_score) {
                update_count += 1;
                best_solution = solution.clone();
            }
        }

        valid_iter += 1;
    }

    eprintln!("===== annealing =====");
    eprintln!("init_score : {}", init_score);
    eprintln!("score      : {}", best_score);
    eprintln!("all iter   : {}", all_iter);
    eprintln!("valid iter : {}", valid_iter);
    eprintln!("accepted   : {}", accepted_count);
    eprintln!("updated    : {}", update_count);
    eprintln!("");

    (best_solution, best_score)
}

fn get_operation(
    input: &Input,
    mut coordinate: Coordinate,
    mut dir: usize,
    mut flag: usize,
    unvisited: &[Coordinate],
    tsp: &[(usize, usize, usize)],
) -> Operation {
    let mut commands = vec![];

    for &(i, next_dir, next_flag) in tsp.iter() {
        let next_coordinate = unvisited[i];
        let next_commands = get_command(
            input,
            coordinate,
            dir,
            flag,
            next_coordinate,
            next_dir,
            next_flag,
        );

        for cmd in next_commands {
            commands.push(cmd);
        }

        coordinate = next_coordinate;
        dir = next_dir;
        flag = next_flag;
    }

    compress_commands(&commands)
}

fn get_command(
    input: &Input,
    start_coordinate: Coordinate,
    start_dir: usize,
    start_flag: usize,
    goal_coordinate: Coordinate,
    goal_dir: usize,
    goal_flag: usize,
) -> Vec<Command> {
    let mut distances = mat![[[100000000; 3]; 4]; N; N];
    let mut from = mat![[[(Coordinate::new(0, 0), 0, 0, Command::F); 3]; 4]; N; N];
    let mut queue = VecDeque::new();
    distances[start_coordinate.row][start_coordinate.col][start_dir][start_flag] = 0;
    queue.push_back((
        start_coordinate.row,
        start_coordinate.col,
        start_dir,
        start_flag,
    ));

    while let Some((row, col, dir, flag)) = queue.pop_front() {
        let dist = distances[row][col][dir][flag];
        let current = Coordinate::new(row, col);

        // Forward
        if let Some(next) = input.graph[row][col][dir] {
            // 9 -> 10の時は考慮できないけどええやろ
            if flag == 2 {
                if chmin!(distances[next.row][next.col][dir][flag], dist) {
                    from[next.row][next.col][dir][flag] = (current, dir, flag, Command::F);
                    queue.push_front((next.row, next.col, dir, flag));
                }
            } else if flag < 2 {
                if chmin!(distances[next.row][next.col][dir][flag + 1], dist + 1) {
                    from[next.row][next.col][dir][flag + 1] = (current, dir, flag, Command::F);
                    queue.push_back((next.row, next.col, dir, flag + 1));
                }
            }
        }

        // Left
        let next_dir = dir.wrapping_sub(1) % 4;
        if chmin!(distances[row][col][next_dir][0], dist + 1) {
            from[row][col][next_dir][0] = (current, dir, flag, Command::L);
            queue.push_back((row, col, next_dir, 0));
        }

        // Right
        let next_dir = (dir + 1) % 4;
        if chmin!(distances[row][col][next_dir][0], dist + 1) {
            from[row][col][next_dir][0] = (current, dir, flag, Command::R);
            queue.push_back((row, col, next_dir, 0));
        }
    }

    let mut current = goal_coordinate;
    let mut dir = goal_dir;
    let mut flag = goal_flag;

    let mut commands = Vec::with_capacity(distances[current.row][current.col][dir][flag]);

    while start_coordinate != current || start_dir != dir || start_flag != flag {
        let (c, d, f, com) = from[current.row][current.col][dir][flag];
        commands.push(com);
        current = c;
        dir = d;
        flag = f;
    }

    commands.reverse();
    commands
}

fn compress_commands(commands: &[Command]) -> Operation {
    let mut last_command = commands[0];
    let mut rep_count = 1;
    let mut operations = vec![];

    for &command in commands.iter().skip(1) {
        if last_command != command {
            operations.push(Operation::Single(rep_count, last_command));
            last_command = command;
            rep_count = 1;
        } else {
            rep_count += 1;
        }
    }

    operations.push(Operation::Single(rep_count, last_command));

    Operation::Multiple(1, operations)
}

fn calc_score(input: &Input, operation: &Operation) -> i32 {
    let (coordinate, direction, cleaned) = generate_init_state(input);
    let (_, _, cleaned_result, _) = operation.apply(input, coordinate, direction, cleaned, 0);

    let cleaned_count = cleaned_result
        .iter()
        .map(|v| v.iter().filter(|&&b| b).count())
        .sum::<usize>();

    if cleaned_count < N * N {
        cleaned_count as i32
    } else {
        let len = operation.to_string().len() as f64;
        let score = (N * N) as i32 + (1e8 / (100.0 + len)).round() as i32;
        score
    }
}

fn to_index(row: usize, col: usize, dir: usize, flag: usize) -> usize {
    (((row * N + col) * 4 + dir) * 3) + flag
}

#[allow(dead_code)]
mod grid {
    #[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
    pub struct Coordinate {
        pub row: usize,
        pub col: usize,
    }

    impl Coordinate {
        pub const fn new(row: usize, col: usize) -> Self {
            Self { row, col }
        }

        pub fn in_map(&self, size: usize) -> bool {
            self.row < size && self.col < size
        }

        pub const fn to_index(&self, size: usize) -> usize {
            self.row * size + self.col
        }
    }

    #[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
    pub struct CoordinateDiff {
        pub dr: usize,
        pub dc: usize,
    }

    impl CoordinateDiff {
        pub const fn new(dr: usize, dc: usize) -> Self {
            Self { dr, dc }
        }

        pub const fn invert(&self) -> Self {
            Self::new(0usize.wrapping_sub(self.dr), 0usize.wrapping_sub(self.dc))
        }
    }

    impl std::ops::Add<CoordinateDiff> for Coordinate {
        type Output = Coordinate;

        fn add(self, rhs: CoordinateDiff) -> Self::Output {
            Coordinate::new(self.row.wrapping_add(rhs.dr), self.col.wrapping_add(rhs.dc))
        }
    }

    pub const ADJACENTS: [CoordinateDiff; 4] = [
        CoordinateDiff::new(!0, 0),
        CoordinateDiff::new(0, 1),
        CoordinateDiff::new(1, 0),
        CoordinateDiff::new(0, !0),
    ];
}

Submission Info

Judge Result