結果

問題 No.659 徘徊迷路
ユーザー arukukaarukuka
提出日時 2018-03-03 00:16:53
言語 D
(dmd 2.106.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,812 KB
testcase_01 AC 7 ms
6,940 KB
testcase_02 AC 1 ms
6,944 KB
testcase_03 WA -
testcase_04 AC 1,762 ms
6,944 KB
testcase_05 AC 2 ms
6,940 KB
testcase_06 AC 1 ms
6,944 KB
testcase_07 AC 2 ms
6,940 KB
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 AC 2 ms
6,940 KB
testcase_13 WA -
testcase_14 AC 13 ms
6,940 KB
testcase_15 AC 13 ms
6,940 KB
testcase_16 WA -
権限があれば一括ダウンロードができます

ソースコード

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