結果

問題 No.659 徘徊迷路
ユーザー cympfhcympfh
提出日時 2018-03-02 23:19:13
言語 Rust
(1.77.0)
結果
AC  
実行時間 41 ms / 2,000 ms
コード長 3,886 bytes
コンパイル時間 3,984 ms
コンパイル使用メモリ 143,756 KB
実行使用メモリ 4,384 KB
最終ジャッジ日時 2023-09-04 11:54:25
合計ジャッジ時間 4,483 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge11
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 5 ms
4,380 KB
testcase_02 AC 1 ms
4,380 KB
testcase_03 AC 1 ms
4,380 KB
testcase_04 AC 3 ms
4,384 KB
testcase_05 AC 1 ms
4,384 KB
testcase_06 AC 1 ms
4,380 KB
testcase_07 AC 1 ms
4,380 KB
testcase_08 AC 5 ms
4,384 KB
testcase_09 AC 10 ms
4,380 KB
testcase_10 AC 20 ms
4,384 KB
testcase_11 AC 38 ms
4,384 KB
testcase_12 AC 3 ms
4,384 KB
testcase_13 AC 34 ms
4,384 KB
testcase_14 AC 34 ms
4,380 KB
testcase_15 AC 41 ms
4,380 KB
testcase_16 AC 40 ms
4,380 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#![allow(unused_imports)]
use std::io::{ self, Write };
use std::str::FromStr;
use std::cmp::{ min, max };
use std::collections::{ BinaryHeap, VecDeque };

#[allow(unused_macros)]
macro_rules! trace {
    ($var:expr) => {
        let _ = writeln!(&mut std::io::stderr(), ">>> {} = {:?}", stringify!($var), $var);
    };
    ($($args:expr),*) => { trace!(($($args),*)) }
}

#[allow(unused_macros)]
macro_rules! put {
    ($var:expr) => {
        let _ = writeln!(&mut std::io::stdout(), "{}", $var);
    };
    ($var:expr, $($args:expr),*) => {
        let _ = write!(&mut std::io::stdout(), "{} ", $var);
        put!($($args),*);
    };
}

type Matrix = Vec<Vec<f64>>;

fn kake(a: &Matrix, b: &Matrix) -> Matrix {
    let n = a.len();
    let mut c: Matrix = vec![vec![0.0; n]; n];
    for i in 0..n {
        for j in 0..n {
            for k in 0..n {
                c[i][j] += a[i][k] * b[k][j];
            }
        }
    }
    c
}

fn eye(n: usize) -> Matrix {
    let mut e: Matrix = vec![vec![0.0; n]; n];
    for i in 0..n { e[i][i] = 1.0; }
    e
}

fn pow(a: &Matrix, n: usize) -> Matrix {
    if n == 0 {
        eye(n)
    } else if n == 1 {
        a.clone()
    } else if n % 2 == 0 {
        let b = kake(a, a);
        pow(&b, n / 2)
    } else {
        let b = kake(a, a);
        let c = pow(&b, (n - 1) / 2);
        kake(&c, a)
    }
}

fn main() {
    let mut sc = Scanner::new();
    let h: usize = sc.cin();
    let w: usize = sc.cin();
    let m: usize = sc.cin();
    let si: usize = sc.cin();
    let sj: usize = sc.cin();
    let gi: usize = sc.cin();
    let gj: usize = sc.cin();

    let mut fs = vec![vec![false; w]; h];
    let mut ids = vec![vec![None; w]; h];

    let n;
    {
        let mut id = 0;
        for i in 0..h {
            let cs: Vec<char> = sc.cin::<String>().chars().collect();
            for j in 0..w {
                if cs[j] == '.' {
                    fs[i][j] = true;
                    ids[i][j] = Some(id);
                    id += 1;
                }
            }
        }
        n = id;
    }
    // for i in 0..h { trace!(fs[i]); }
    // for i in 0..h { trace!(ids[i]); }

    let mut d = vec![vec![0.0; n]; n];

    for i in 0..h {
        for j in 0..w {
            if fs[i][j] {
                let id = ids[i][j].unwrap();
                let mut ps = vec![];
                if fs[i-1][j] { ps.push((i-1, j)); }
                if fs[i+1][j] { ps.push((i+1, j)); }
                if fs[i][j-1] { ps.push((i, j-1)); }
                if fs[i][j+1] { ps.push((i, j+1)); }
                if ps.len() == 0 {
                    d[id][id] = 1.0;
                } else {
                    let q: f64 = 1.0 / (ps.len() as f64);
                    for &p in ps.iter() {
                        let (i2, j2) = p;
                        let id2 = ids[i2][j2].unwrap();
                        d[id][id2] = q;
                    }
                }
            }
        }
    }
    // for i in 0..n { trace!(d[i]); }
    let dm = pow(&d, m);
    // for i in 0..n { trace!(dm[i]); }
    {
        let s = ids[si][sj].unwrap();
        let t = ids[gi][gj].unwrap();
        put!(dm[s][t]);
    }
}

#[allow(dead_code)]
struct Scanner { stdin: io::Stdin, buffer: VecDeque<String>, }
#[allow(dead_code)]
impl Scanner {
    fn new() -> Scanner { Scanner { stdin: io::stdin(), buffer: VecDeque::new() } }
    fn reserve(&mut self) {
        while self.buffer.len() == 0 {
            let mut line = String::new();
            let _ = self.stdin.read_line(&mut line);
            for w in line.split_whitespace() {
                self.buffer.push_back(String::from(w));
            }
        }
    }
    fn cin<T: FromStr>(&mut self) -> T {
        self.reserve();
        match self.buffer.pop_front().unwrap().parse::<T>() {
            Ok(a) => a,
            Err(_) => panic!("parse err")
        }
    }
}
0