結果

問題 No.659 徘徊迷路
ユーザー anta
提出日時 2018-03-02 22:34:23
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 65 ms / 2,000 ms
コード長 2,452 bytes
コンパイル時間 2,560 ms
コンパイル使用メモリ 180,296 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-13 03:56:01
合計ジャッジ時間 4,250 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include "bits/stdc++.h"
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
template<typename T, typename U> static void amin(T &x, U y) { if (y < x) x = y; }
template<typename T, typename U> static void amax(T &x, U y) { if (x < y) x = y; }

using Num = double;
struct Matrix {
	vector<vector<Num> > v, w;
	Matrix() {}
	Matrix(int n, int m) : v(n, vector<Num>(m)) { }
	inline int height() const { return (int)v.size(); }
	inline int width() const { return (int)v[0].size(); }
	inline Num& at(int i, int j) { return v[i][j]; }
	inline const Num& at(int i, int j) const { return v[i][j]; }
	static Matrix identity(int n) {
		Matrix A(n, n);
		rep(i, n) A.at(i, i) = 1;
		return A;
	}
	inline static Matrix identity(const Matrix& A) { return identity(A.height()); }
	Matrix& operator*=(const Matrix& B) {
		int n = height(), m = B.width(), p = B.height();
		assert(p == width());
		w.assign(n, vector<Num>(m, 0));
		rep(i, n) rep(j, m) {
			Num x = 0;
			rep(k, p) x += at(i, k) * B.at(k, j);
			w[i][j] = x;
		}
		v.swap(w);
		return *this;
	}
};
Matrix operator^(const Matrix& t, ll k) {
	Matrix A = t, B = Matrix::identity(t);
	while (k) {
		if (k & 1) B *= A;
		A *= A;
		k >>= 1;
	}
	return B;
}

int main() {
	int H; int W; int T;
	while (~scanf("%d%d%d", &H, &W, &T)) {
		int sy; int sx;
		scanf("%d%d", &sy, &sx);
		int gy; int gx;
		scanf("%d%d", &gy, &gx);
		vector<string> maze(H);
		rep(i, H) {
			char buf[101];
			scanf("%s", buf);
			maze[i] = buf;
		}
		Matrix A(H * W, H * W);
		rep(i, H) rep(j, W) if(maze[i][j] != '#') {
			static const int dy[4] = { 0, 1, 0, -1 }, dx[4] = { 1, 0, -1, 0 };
			vector<int> next;
			for (int d = 0; d < 4; ++ d) {
				int yy = i + dy[d], xx = j + dx[d];
				if (yy < 0 || yy >= H || xx < 0 || xx >= W) continue;
				if (maze[yy][xx] == '#') continue;
				next.push_back(yy * W + xx);
			}
			int cur = i * W + j;
			if (next.empty()) {
				A.at(cur, cur) += 1;
			} else {
				double p = 1. / next.size();
				for (int t : next)
					A.at(cur, t) += p;
			}
		}
		A = A ^ T;
		auto ans = A.at(sy * W + sx, gy * W + gx);
		printf("%.10f\n", ans);
	}
	return 0;
}
0