結果
問題 | No.659 徘徊迷路 |
ユーザー | cympfh |
提出日時 | 2018-03-02 23:19:13 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 34 ms / 2,000 ms |
コード長 | 3,886 bytes |
コンパイル時間 | 14,238 ms |
コンパイル使用メモリ | 391,824 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-06-22 10:39:31 |
合計ジャッジ時間 | 13,923 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
5,248 KB |
testcase_01 | AC | 5 ms
5,376 KB |
testcase_02 | AC | 1 ms
5,376 KB |
testcase_03 | AC | 1 ms
5,376 KB |
testcase_04 | AC | 3 ms
5,376 KB |
testcase_05 | AC | 1 ms
5,376 KB |
testcase_06 | AC | 0 ms
5,376 KB |
testcase_07 | AC | 1 ms
5,376 KB |
testcase_08 | AC | 3 ms
5,376 KB |
testcase_09 | AC | 8 ms
5,376 KB |
testcase_10 | AC | 16 ms
5,376 KB |
testcase_11 | AC | 32 ms
5,376 KB |
testcase_12 | AC | 4 ms
5,376 KB |
testcase_13 | AC | 29 ms
5,376 KB |
testcase_14 | AC | 28 ms
5,376 KB |
testcase_15 | AC | 34 ms
5,376 KB |
testcase_16 | AC | 34 ms
5,376 KB |
ソースコード
#![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")}}}