結果

問題 No.2913 二次元距離空間
ユーザー atcoder8atcoder8
提出日時 2024-10-04 23:25:15
言語 Rust
(1.77.0 + proconio)
結果
AC  
実行時間 114 ms / 2,000 ms
コード長 2,267 bytes
コンパイル時間 17,642 ms
コンパイル使用メモリ 402,492 KB
実行使用メモリ 9,088 KB
最終ジャッジ日時 2024-10-04 23:25:34
合計ジャッジ時間 15,595 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 0 ms
6,820 KB
testcase_01 AC 1 ms
6,820 KB
testcase_02 AC 1 ms
6,816 KB
testcase_03 AC 1 ms
6,820 KB
testcase_04 AC 1 ms
6,820 KB
testcase_05 AC 1 ms
6,816 KB
testcase_06 AC 1 ms
6,816 KB
testcase_07 AC 1 ms
6,820 KB
testcase_08 AC 1 ms
6,816 KB
testcase_09 AC 1 ms
6,820 KB
testcase_10 AC 1 ms
6,816 KB
testcase_11 AC 1 ms
6,820 KB
testcase_12 AC 1 ms
6,816 KB
testcase_13 AC 1 ms
6,820 KB
testcase_14 AC 1 ms
6,816 KB
testcase_15 AC 1 ms
6,820 KB
testcase_16 AC 13 ms
9,088 KB
testcase_17 AC 17 ms
8,960 KB
testcase_18 AC 83 ms
9,088 KB
testcase_19 AC 114 ms
9,088 KB
testcase_20 AC 79 ms
9,088 KB
testcase_21 AC 7 ms
8,832 KB
testcase_22 AC 6 ms
8,960 KB
testcase_23 AC 93 ms
9,088 KB
testcase_24 AC 7 ms
8,960 KB
testcase_25 AC 95 ms
9,088 KB
testcase_26 AC 7 ms
8,960 KB
testcase_27 AC 102 ms
9,088 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

use std::{cmp::Reverse, collections::BinaryHeap};

use proconio::{input, marker::Chars};

const DIFFS: [(usize, usize); 4] = [(!0, 0), (0, !0), (0, 1), (1, 0)];

fn main() {
    input! {
        (h, w): (usize, usize),
        ss: [Chars; h],
    }

    let mut cost_matrix: Vec<Vec<Option<(usize, usize)>>> = vec![vec![None; w]; h];
    let mut heap = BinaryHeap::from([Reverse(Node {
        horizontal_cost: 0,
        vertical_cost: 0,
        coord: (0, 0),
    })]);
    while let Some(Reverse(node)) = heap.pop() {
        let (row, col) = node.coord;

        if cost_matrix[row][col].is_some() {
            continue;
        }

        cost_matrix[row][col] = Some((node.horizontal_cost, node.vertical_cost));

        for (diff_row, diff_col) in DIFFS {
            let adj_row = row.wrapping_add(diff_row);
            let adj_col = col.wrapping_add(diff_col);
            let adj_coord = (adj_row, adj_col);

            if adj_row < h && adj_col < w && ss[adj_row][adj_col] == '.' {
                let next_node = Node {
                    horizontal_cost: node.horizontal_cost + (diff_col != 0) as usize,
                    vertical_cost: node.vertical_cost + (diff_row != 0) as usize,
                    coord: adj_coord,
                };
                heap.push(Reverse(next_node));
            }
        }
    }

    match cost_matrix[h - 1][w - 1] {
        Some((horizontal_cost, vertical_cost)) => {
            println!("Yes\n{} {}", horizontal_cost, vertical_cost)
        }
        None => println!("No"),
    }
}

struct Node {
    horizontal_cost: usize,
    vertical_cost: usize,
    coord: (usize, usize),
}

impl PartialEq for Node {
    fn eq(&self, other: &Self) -> bool {
        self.horizontal_cost == other.horizontal_cost && self.vertical_cost == other.vertical_cost
    }
}

impl Eq for Node {}

impl PartialOrd for Node {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        Some(self.cmp(other))
    }
}

impl Ord for Node {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        match self.horizontal_cost.cmp(&other.horizontal_cost) {
            core::cmp::Ordering::Equal => {}
            ord => return ord,
        }
        self.vertical_cost.cmp(&other.vertical_cost)
    }
}
0