結果

問題 No.659 徘徊迷路
コンテスト
ユーザー sekiya9311
提出日時 2018-03-04 20:53:37
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 114 ms / 2,000 ms
コード長 2,135 bytes
コンパイル時間 1,679 ms
コンパイル使用メモリ 179,040 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-08 14:06:55
合計ジャッジ時間 3,531 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;

const int dx[] = {0, 0, -1, 1};
const int dy[] = {1, -1, 0, 0};

using row = std::vector<long double>;
using matrix = std::vector<row>;
//(A * B) mod
matrix matrixMul(matrix &A, matrix &B, const int mod) {
    const int asz = A.size();
    const int bsz = B.size();
    const int bcolsz = B.front().size();
    matrix res(asz, row(bcolsz, 0));
    for (int i = 0; i < asz; i++) {
        for (int k = 0; k < bsz; k++) {
            for (int j = 0; j < bcolsz; j++) {
                (res[i][j] += A[i][k] * B[k][j]);
            }
        }
    }
    return res;
}
//(mat^p) mod
matrix matPowMod(matrix mat, long long p, const int mod) {
    const int matsz = mat.size();
    assert((int)mat.front().size() == matsz);//must square matrix!!
    matrix res(matsz, row(matsz, 0));
    for (int i = 0; i < matsz; i++) {
        res[i][i] = 1;
    }
    while (p) {
        if (p & 1) res = matrixMul(res, mat, mod);
        mat = matrixMul(mat, mat, mod);
        p >>= 1;
    }
    return res;
}

matrix make_matrix(int r, int c) {
    return matrix(r, row(c));
}

int main() {
    int r, c, t;
    cin >> r >> c >> t;
    int sy, sx, gy, gx;
    cin >> sy >> sx >> gy >> gx;
    auto mat = make_matrix(100, 100);
    vector<string> B(r);
    for_each(begin(B), end(B), [](auto &e){cin >> e;});
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            const int rIdx = i * 10 + j;
            if (B[i][j] == '.') {
                int cnt = 0;
                for (int k = 0; k < 4; k++) {
                    cnt += B[i + dy[k]][j + dx[k]] == '.';
                }
                if (cnt) {
                    for (int k = 0; k < 4; k++) {
                        const int cIdx = (i + dy[k]) * 10 + j + dx[k];
                        mat[rIdx][cIdx] = 1. * (B[i + dy[k]][j + dx[k]] == '.') / cnt;
                    }
                } else {
                    mat[rIdx][rIdx] = 1;
                }
            }
        }
    }
    auto mat2 = matPowMod(mat, t, -1);
    cout << fixed << setprecision(10) << mat2[sy * 10 + sx][gy * 10 + gx] << endl;;
}
0