結果

問題 No.659 徘徊迷路
ユーザー kyunakyuna
提出日時 2019-08-20 15:31:34
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 67 ms / 2,000 ms
コード長 2,679 bytes
コンパイル時間 1,102 ms
コンパイル使用メモリ 88,380 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-10-06 12:26:11
合計ジャッジ時間 2,470 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
6,820 KB
testcase_01 AC 16 ms
6,820 KB
testcase_02 AC 3 ms
6,820 KB
testcase_03 AC 2 ms
6,816 KB
testcase_04 AC 21 ms
6,816 KB
testcase_05 AC 3 ms
6,816 KB
testcase_06 AC 3 ms
6,820 KB
testcase_07 AC 2 ms
6,816 KB
testcase_08 AC 25 ms
6,820 KB
testcase_09 AC 57 ms
6,820 KB
testcase_10 AC 65 ms
6,820 KB
testcase_11 AC 65 ms
6,816 KB
testcase_12 AC 14 ms
6,820 KB
testcase_13 AC 57 ms
6,816 KB
testcase_14 AC 57 ms
6,816 KB
testcase_15 AC 67 ms
6,816 KB
testcase_16 AC 67 ms
6,820 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

template<class T> ostream& operator<<(ostream& os, const vector<T>& vec) {
    for (auto &vi: vec) os << vi << " "; return os;
}
template<class T> struct Matrix {
    vector<vector<T>> val;
    Matrix(int n = 1, int m = 1, T x = 0) { val.assign(n, vector<T>(m, x)); }
    size_t size() const { return val.size(); }
    vector<T>& operator[](int i) { return val[i]; }
    const vector<T>& operator[](int i) const { return val[i]; }
    friend ostream& operator<<(ostream& os, const Matrix<T> M) {
        for (int i = 0; i < M.size(); ++i) os << M[i] << " \n"[i != M.size() - 1];
        return os;
    }
};
template<class T> Matrix<T> operator^(Matrix<T> A, long long n) {
    Matrix<T> R(A.size(), A.size());
    for (int i = 0; i < A.size(); ++i) R[i][i] = 1;
    while (n > 0) { if (n & 1) R = R * A; A = A * A; n >>= 1; }
    return R;
}
template<class T> Matrix<T> operator*(const Matrix<T>& A, const Matrix<T>& B) {
    Matrix<T> R(A.size(), B[0].size());
    for (int i = 0; i < A.size(); ++i) for (int j = 0; j < B[0].size(); ++j)
        for (int k = 0; k < B.size(); ++k) R[i][j] += A[i][k] * B[k][j];
    return R;
}
template<class T> vector<T> operator*(const Matrix<T> &A, vector<T> &B) {
    vector<T> v(A.size());
    for (int i = 0; i < A.size(); ++i)
        for (int k = 0; k < B.size(); ++k) v[i] += A[i][k] * B[k];
    return v;
}

#include <iomanip>
int dij[] = { 0, -1, 0, 1, 0 };
int main() {
    cout << fixed << setprecision(12);
    int H, W, T; cin >> H >> W >> T;
    int si, sj, gi, gj; cin >> si >> sj >> gi >> gj;
    vector<string> field(H);
    for (string &s: field) cin >> s;
    Matrix<double> trans(H * W, H * W);
    auto idx = [&](int i, int j) { return i * W + j; };
    for (int i = 0; i < H; i++) for (int j = 0; j < W; j++) {
        if (field[i][j] == '#') continue;
        int cnt = 0;
        for (int k = 0; k < 4; k++) {
            int ni = i + dij[k], nj = j + dij[k + 1];
            if (ni < 0 || ni >= H || nj < 0 || nj >= W) continue;
            if (field[ni][nj] == '#') continue;
            cnt++;
        }
        if (cnt == 0) {
            trans[idx(i, j)][idx(i, j)] = 1.0;
        } else {
            for (int k = 0; k < 4; k++) {
                int ni = i + dij[k], nj = j + dij[k + 1];
                if (ni < 0 || ni >= H || nj < 0 || nj >= W) continue;
                if (field[ni][nj] == '#') continue;
                trans[idx(ni, nj)][idx(i, j)] = 1.0 / cnt;
            }
        }
    }
    vector<double> state(H * W);
    state[idx(si, sj)] = 1;
    cout << ((trans ^ T) * state)[idx(gi, gj)] << endl;
    return 0;
}
0