R, C, T = gets.split.map &:to_i Sy, Sx = gets.split.map &:to_i Gy, Gx = gets.split.map &:to_i Board = $<.map{|s|s.chomp.chars} DIRS = [[1,0],[-1,0],[0,1],[0,-1]] BITS_COUNT = [ 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, ] flags = R.times.map{ [0]*C } (1...R).each{|y| (1...C).each{|x| next if Board[y][x] == ?# flags[y][x] = DIRS.map.with_index{|(dy, dx), i| Board[y+dy][x+dx] == ?# ? 0 : 1 << i }.inject :| } } state = R.times.map{ [0.0]*C } dp = state.map &:dup dp[Sy][Sx] = 1.0 [T, 10000+T%2].min.times{ next_dp = state.map &:dup (1...R).each{|y| (1...C).each{|x| next if Board[y][x] == ?# dir_count = BITS_COUNT[flags[y][x]] if dir_count == 0 next_dp[y][x] += dp[y][x] next end DIRS.each_with_index{|(dy, dx), d| next if flags[y][x] & (1 << d) == 0 next_dp[y+dy][x+dx] += dp[y][x] / dir_count } } } dp = next_dp } p dp[Gy][Gx].to_f