結果

問題 No.659 徘徊迷路
ユーザー pekempeypekempey
提出日時 2018-03-02 22:51:11
言語 Rust
(1.77.0)
結果
AC  
実行時間 129 ms / 2,000 ms
コード長 1,959 bytes
コンパイル時間 3,471 ms
コンパイル使用メモリ 148,408 KB
実行使用メモリ 4,388 KB
最終ジャッジ日時 2023-09-04 05:18:54
合計ジャッジ時間 5,361 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 27 ms
4,380 KB
testcase_02 AC 1 ms
4,388 KB
testcase_03 AC 1 ms
4,376 KB
testcase_04 AC 40 ms
4,380 KB
testcase_05 AC 2 ms
4,380 KB
testcase_06 AC 2 ms
4,380 KB
testcase_07 AC 2 ms
4,380 KB
testcase_08 AC 46 ms
4,380 KB
testcase_09 AC 109 ms
4,380 KB
testcase_10 AC 125 ms
4,384 KB
testcase_11 AC 125 ms
4,380 KB
testcase_12 AC 23 ms
4,380 KB
testcase_13 AC 109 ms
4,376 KB
testcase_14 AC 109 ms
4,380 KB
testcase_15 AC 129 ms
4,380 KB
testcase_16 AC 128 ms
4,380 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

type Mat = Vec<Vec<f64>>;

fn main() {
  let h: usize = input();
  let w: usize = input();
  let t: usize = input();

  let sy: usize = input();
  let sx: usize = input();
  let gy: usize = input();
  let gx: usize = input();

  let mut g: Vec<Vec<u8>> = vec![Vec::new(); h];
  for i in 0..h {
    g[i] = input::<String>().into_bytes();
  }
  let g = g;

  let n: usize = h * w;
  let mut mat: Mat = vec![vec![0.0; n]; n]; 

  for i in 1..h - 1 {
    for j in 1..w - 1 {
      let mut cnt = 0;
      for &(ni, nj) in &[(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)] {
        if g[ni][nj] == b'.' {
          cnt += 1;
        }
      }
      if cnt > 0 {
        for &(ni, nj) in &[(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)] {
          if g[ni][nj] == b'.' {
            mat[ni * w + nj][i * w + j] += 1.0 / (cnt as f64);
          }
        }
      } else {
        mat[i * w + j][i * w + j] = 1.0;
      }
    }
  }

  mat = matpow(mat, t);

  println!("{:20}", mat[gy * w + gx][sy * w + sx]);
}

fn matpow(mut a: Mat, mut b: usize) -> Mat {
  let n: usize = a.len();
  let mut res: Mat = vec![vec![0.0; n]; n];
  for i in 0..n {
    res[i][i] = 1.0;
  }
  while b > 0 {
    if b % 2 == 1 {
      res = matmul(&res, &a);
    }
    a = matmul(&a, &a);
    b >>= 1;
  }
  res
}

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

fn input<T: std::str::FromStr>() -> T {
  use std::io::Read;
  let stdin = std::io::stdin();
  let stdin = stdin.bytes();
  let token = stdin
    .skip_while(|x| (*x.as_ref().unwrap() as char).is_whitespace())
    .take_while(|x| !(*x.as_ref().unwrap() as char).is_whitespace())
    .map(|x| x.unwrap())
    .collect();
  let token = String::from_utf8(token).unwrap();
  match token.parse() {
    Ok(x) => x,
    Err(_) => panic!("{}", token),
  }
}
0