結果

問題 No.659 徘徊迷路
ユーザー pazzle1230pazzle1230
提出日時 2018-03-02 23:08:58
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 129 ms / 2,000 ms
コード長 2,159 bytes
コンパイル時間 2,197 ms
コンパイル使用メモリ 179,840 KB
実行使用メモリ 6,332 KB
最終ジャッジ日時 2023-09-04 06:46:16
合計ジャッジ時間 4,284 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4 ms
4,380 KB
testcase_01 AC 84 ms
5,992 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 AC 2 ms
4,376 KB
testcase_04 AC 38 ms
5,488 KB
testcase_05 AC 5 ms
4,380 KB
testcase_06 AC 5 ms
4,380 KB
testcase_07 AC 2 ms
4,380 KB
testcase_08 AC 118 ms
6,088 KB
testcase_09 AC 122 ms
6,244 KB
testcase_10 AC 127 ms
6,260 KB
testcase_11 AC 127 ms
6,264 KB
testcase_12 AC 115 ms
6,044 KB
testcase_13 AC 120 ms
6,240 KB
testcase_14 AC 117 ms
6,136 KB
testcase_15 AC 129 ms
6,184 KB
testcase_16 AC 127 ms
6,332 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

#define INF_LL (ll)1e18
#define INF (int)1e9
#define REP(i, n) for(int i = 0;i < (n);i++)
#define FOR(i, a, b) for(int i = (a);i < (b);i++)
#define all(x) x.begin(),x.end()
#define fs first
#define sc second

using int32 = int_fast32_t;
using uint32 = uint_fast32_t;
using int64 = int_fast64_t;
using uint64 = uint_fast64_t;
using PII = pair<int32, int32>;
using PLL = pair<int64, int64>;

const double eps = 1e-10;

template<typename A, typename B>inline void chmin(A &a, B b){if(a > b) a = b;}
template<typename A, typename B>inline void chmax(A &a, B b){if(a < b) a = b;}

double table[10][10][10][10][32] = {};
int32 dx[4] = {-1, 0, 0, 1};
int32 dy[4] = {0, -1, 1, 0};
int64 sx, sy, gx, gy;
int64 R, C, T;
map<tuple<int32, int32, int32>, double> mp;

double dfs(int32 py, int32 px, int64 rest){
	if(mp[{py, px, rest}]) return mp[{py, px, rest}] == -1 ? 0 : mp[{py, px,rest}];
	int32 cnt = 0, bit = 1;
	while(bit <= rest){
		bit*=2;
		cnt++;
	}
	bit /= 2;
	cnt--;
	if(rest == bit){
		if(table[py][px][gy][gx][cnt] == 0){
			mp[{py, px, rest}] = -1;
			return 0;
		}else{
			return mp[{py, px, rest}] = table[py][px][gy][gx][cnt];
		}
	}

	double res = 0;
	REP(i, R){
		REP(j, C){
			res += table[py][px][i][j][cnt]*dfs(i, j, rest-bit);
		}
	}
	if(res == 0){
		mp[{py, px, rest}] = -1;
		return 0;
	}else{
		return mp[{py, px, rest}] = res;
	}
}

int main(void){
	cin >> R >> C >> T;
	cin >> sy >> sx >> gy >> gx;
	string f[10];
	REP(i, R)
		cin >> f[i];

	FOR(i, 1, R-1){
		FOR(j, 1, C-1){
			if(f[i][j] == '#') continue;
			int32 cnt = 0;
			REP(k, 4){
				int32 yy = i+dy[k], xx = j+dx[k];
				if(f[yy][xx] == '.') cnt++;
			}
			REP(k, 4){
				int32 yy = i+dy[k], xx = j+dx[k];
				if(f[yy][xx] == '.'){
					table[i][j][yy][xx][0] = 1.0/(double)cnt;
				}
			}
			if(cnt == 0)
				table[i][j][i][j][0] = 1;
		}
	}

	REP(t, 31){
		REP(i, R){
			REP(j, C){
				REP(k, R){
					REP(l, C){
						REP(m, R){
							REP(n, C){
								table[i][j][k][l][t+1] += table[i][j][m][n][t]*table[m][n][k][l][t];
							}
						}
					}
				}
			}
		}
	}
	
	cout << fixed << setprecision(10) << dfs(sy, sx, T) << endl;
}
0