type Mat = Vec>; 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![Vec::new(); h]; for i in 0..h { g[i] = input::().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 { 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), } }