結果
| 問題 | No.659 徘徊迷路 |
| ユーザー |
 fiord
|
| 提出日時 | 2018-03-04 00:45:50 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 694 ms / 2,000 ms |
| コード長 | 4,127 bytes |
| コンパイル時間 | 1,556 ms |
| コンパイル使用メモリ | 127,312 KB |
| 実行使用メモリ | 5,376 KB |
| 最終ジャッジ日時 | 2024-07-05 05:41:55 |
| 合計ジャッジ時間 | 6,777 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 5 |
| other | AC * 12 |
ソースコード
#define _USE_MATH_DEFINES#include <iostream>#include <fstream>#include <cstdio>#include <cmath>#include <cstdlib>#include <cstring>#include <cassert>#include <string>#include <vector>#include <utility>#include <complex>#include <set>#include <map>#include <queue>#include <stack>#include <deque>#include <tuple>#include <bitset>#include <limits>#include <algorithm>#include <random>#include <complex>#include <regex>using namespace std;typedef long double ld;typedef long long ll;typedef vector<int> vint;typedef pair<int, int> pii;typedef pair<ll, ll> pll;typedef pair<double, double> pdd;typedef complex<ld> compd;#define reach(i,a) for(auto i:a)#define rep(i,n) for(int i=0;i<(int)n;i++)#define REP(i,n) for(int i=0;i<=(int)n;i++)#define srep(i,a,n) for(int i=a;i<(int)n;i++)#define SREP(i,a,n) for(int i=a;i<=(int)n;i++)#define rrep(i,n) for(int i=n-1;i>=0;i--)#define RREP(i,n) for(int i=n;i>=0;i--)#define all(a) (a).begin(),(a).end()#define mp(a,b) make_pair(a,b)#define mt make_tuple#define pb push_back#define fst first#define scn secondint bitcnt(ll x) {x = ((x & 0xAAAAAAAAAAAAAAAA) >> 1) + (x & 0x5555555555555555);x = ((x & 0xCCCCCCCCCCCCCCCC) >> 2) + (x & 0x3333333333333333);x = ((x & 0xF0F0F0F0F0F0F0F0) >> 4) + (x & 0x0F0F0F0F0F0F0F0F);x = ((x & 0xFF00FF00FF00FF00) >> 8) + (x & 0x00FF00FF00FF00FF);x = ((x & 0xFFFF0000FFFF0000) >> 16) + (x & 0x0000FFFF0000FFFF);x = ((x & 0xFFFFFFFF00000000) >> 32) + (x & 0x00000000FFFFFFFF);return x;}int bitcnt(int x) {x = ((x & 0xAAAAAAAA) >> 1) + (x & 0x55555555);x = ((x & 0xCCCCCCCC) >> 2) + (x & 0x33333333);x = ((x & 0xF0F0F0F0) >> 4) + (x & 0x0F0F0F0F);x = ((x & 0xFF00FF00) >> 8) + (x & 0x00FF00FF);x = ((x & 0xFFFF0000) >> 16) + (x & 0x0000FFFF);return x;}ll gcd(ll a, ll b) {return a%b == 0 ? b : gcd(b, a%b);}#define debug(x) cout<<"case #" << x << ": " << endl#define DEBUG 0const ll inf = 1e9;const ll mod = 1e9 + 7;const ld eps = 1e-15;const int dx[] = { 1,0,-1,0,0 };const int dy[] = { 0,1,0,-1,0 };int r, c, t;int sx, sy, gx, gy;vector<string> mp;// 確率ld ret[10][10],tmp[10][10];// 行先(i,j)->(k,l)の遷移確率（何ターンで移動するかは更新していく）ld nxt[10][10][10][10], nxt2[10][10][10][10];bool isInside(int y, int x) {if (y < 0 || r <= y) return false;if (x < 0 || c <= x) return false;return true;}int main() {cin >> r >> c >> t;cin >> sy >> sx;cin >> gy >> gx;mp.resize(r);rep(i, r) cin >> mp[i];ret[sy][sx] = 1.0;while (t > 0) {// nxtの初期化rep(i, r) rep(j, c){if (mp[i][j] == '#') continue;rep(k, r) rep(l, c) nxt[i][j][k][l] = 0.0;int cnt = 0;rep(k, 4) {if (!isInside(i + dy[k], j + dx[k])) continue;if (mp[i + dy[k]][j + dx[k]] == '#') continue;cnt++;}if (cnt == 0) nxt[i][j][i][j] = 1.0;else {rep(k, 4) {if (!isInside(i + dy[k], j + dx[k])) continue;if (mp[i + dy[k]][j + dx[k]] == '#') continue;nxt[i][j][i + dy[k]][j + dx[k]] = 1.0 / cnt;}}}// 最初に1ターン進める（nxtの更新はしない）int add = 1;rep(i, r) rep(j, c) {if (ret[i][j] < eps) continue;rep(k, 5) {if (!isInside(i + dy[k], j + dx[k])) continue;tmp[i + dy[k]][j + dx[k]] += ret[i][j] * nxt[i][j][i + dy[k]][j + dx[k]];}}rep(i, r) rep(j, c) {ret[i][j] = tmp[i][j];tmp[i][j] = 0.0;}while (t - add * 2 >= 0) {// nxtに沿って確率の更新rep(i, r) rep(j, c){if (ret[i][j] < eps) continue;rep(k, r) rep(l, c) {tmp[k][l] += ret[i][j] * nxt[i][j][k][l];}}rep(i, r) rep(j, c) {ret[i][j] = tmp[i][j] + eps;tmp[i][j] = 0.0;}add <<= 1;// nxtの更新rep(i, r) rep(j, c) rep(k, r) rep(l, c) {if (nxt[i][j][k][l] < eps) continue;rep(a, r) rep(b, c) {nxt2[i][j][a][b] += nxt[i][j][k][l] * nxt[k][l][a][b];}}rep(i, r) rep(j, c) rep(k, r) rep(l, c) {nxt[i][j][k][l] = nxt2[i][j][k][l] + eps;nxt2[i][j][k][l] = 0.0;}}t -= add;}printf("%.15Lf\n", ret[gy][gx]+eps);return 0;}