結果

問題 No.659 徘徊迷路
ユーザー arukukaarukuka
提出日時 2018-03-03 00:16:53
言語 D
(dmd 2.109.1)
結果
WA  
実行時間 -
コード長 1,596 bytes
コンパイル時間 2,315 ms
コンパイル使用メモリ 157,008 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-06-13 00:01:19
合計ジャッジ時間 5,167 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4 WA * 1
other AC * 6 WA * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

import std.stdio;
import std.range;
import std.array;
import std.string;
import std.conv;
import std.typecons;
import std.algorithm;
import std.container;
import std.typecons;
import std.random;
import core.time;

void main()
{
	auto f = readln.chomp.split.map!(to!int);
	int r, c, t;
	r = f[0];
	c = f[1];
	t = f[2];
	int[] s = readln.chomp.split.map!(to!int).retro.array;
	int[] g = readln.chomp.split.map!(to!int).retro.array;
	double[][][] prob = new double[][][](2, r, c);
	string[] field;
	foreach (y; 0..r) {
		field ~= readln.chomp;
	}
	bool reached = false;
	bool[string[]] set;
	foreach (ref v; prob[0]) {
		v []= 0.0;
	}
	prob[0][s[1]][s[0]] = 1;
	foreach (i; 0..min(t, 100000)) {
		foreach (y; 0..r) {
			prob[1 - i % 2][y] []= 0.0;
		}
		foreach (y; 0..r) {
			foreach (x; 0..c) {
				if (field[y][x] == '#') {
					continue;
				}
				int p = 0;
				enum OFS = [
					[0, 1],
					[1, 0],
					[-1, 0],
					[0, -1]
				];
				foreach (D; OFS) {
					auto nx = x + D[0];
					auto ny = y + D[1];
					if (field[ny][nx] == '#') {
						continue;
					}
					++p;
				}
				foreach (D; OFS) {
					auto nx = x + D[0];
					auto ny = y + D[1];
					if (field[ny][nx] == '#') {
						continue;
					}
					prob[1 - i % 2][ny][nx] += (1.0 / p) * prob[i % 2][y][x];
				}
			}
		}
		reached |= prob[1 - i % 2][g[1]][g[0]] > 0;
		if (reached) {
			auto arr = [format("%.7f", prob[i % 2][g[1]][g[0]]), format("%.7f", prob[1 - i % 2][g[1]][g[0]])];
			if (arr in set) {
				arr[0].writeln;
				return;
			}
			set[arr.idup] = true;
		}
	}
	format("%.7f", prob[t % 2][g[1]][g[0]]).writeln;
}
0