結果

問題 No.659 徘徊迷路
ユーザー cympfhcympfh
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

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")
}
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0