結果

問題 No.659 徘徊迷路
ユーザー arukukaarukuka
提出日時 2018-03-03 00:30:43
言語 D
(dmd 2.106.1)
結果
AC  
実行時間 126 ms / 2,000 ms
コード長 2,215 bytes
コンパイル時間 2,360 ms
コンパイル使用メモリ 158,768 KB
実行使用メモリ 17,000 KB
最終ジャッジ日時 2024-06-13 00:02:45
合計ジャッジ時間 2,906 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

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;
	}
	alias Point = Tuple!(int, "x", int, "y");
	bool[Point] done;
	Point[] queue;
	queue ~= Point(s[0], s[1]);
	enum OFS = [
		[0, 1],
		[1, 0],
		[-1, 0],
		[0, -1]
	];
	while (queue.length) {
		Point node = queue[0];
		queue = queue[1..$];
		if (node in done) {
			continue;
		}
		done[node] = true;
		foreach (D; OFS) {
			Point next = Point(node.x + D[0], node.y + D[1]);
			if (field[next.y][next.x] == '#') {
				continue;
			}
			queue ~= next;
		}
	}
	if (Point(g[0], g[1]) !in done) {
		0.writeln;
		return;
	}
	bool reached = false;
	bool[string[]] set;
	foreach (ref v; prob[0]) {
		v []= 0.0;
	}
	prob[0][s[1]][s[0]] = 1;
	foreach (i; 0..t) {
		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;
				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];
				}
				if (p == 0) {
					prob[1 - i % 2][y][x] = prob[i % 2][y][x];
				}
			}
		}
		reached |= format("%.9f", prob[1 - i % 2][g[1]][g[0]]) != "0.000000000";
		if (reached) {
			auto arr = [format("%.9f", prob[i % 2][g[1]][g[0]]), format("%.9f", prob[1 - i % 2][g[1]][g[0]])];
			// arr.writeln;
			if (arr in set) {
				// stderr.writeln(t, ", ", t % 2, ", ", i, ", ", i % 2);
				arr[t % 2 ^ i % 2].writeln;
				return;
			}
			set[arr.idup] = true;
		}
	}
	format("%.9f", prob[t % 2][g[1]][g[0]]).writeln;
}
0