結果

問題 No.659 徘徊迷路
コンテスト
ユーザー Kutimoti_T
提出日時 2018-06-23 19:59:59
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 42 ms / 2,000 ms
コード長 2,553 bytes
コンパイル時間 1,466 ms
コンパイル使用メモリ 167,104 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-30 18:32:31
合計ジャッジ時間 2,555 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(int (i) = (s);(i) <= (e);(i)++)

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

template <class T>
struct Matrix {
  vector<vector<T>> value;
  T init;

  Matrix(vector<vector<T>> vec, T init_) : init(init_), value(vec) {}
  Matrix(int h, int w, T init_) : init(init_), value(h, vector<T>(w, init_)) {}

  Matrix<T> operator*(Matrix<T>& left) {
    Matrix<T> res(value.size(), left[0].size(), init);
    for (int i = 0; i < value.size(); i++) {
      for (int k = 0; k < left.size(); k++) {
        for (int j = 0; j < left[0].size(); j++) {
          res[i][j] = (res[i][j] + value[i][k] * left[k][j]);
        }
      }
    }
    return res;
  }

  Matrix<T> operator+(Matrix<T>& left) {
    Matrix<T> res = *this;
    for (int i = 0; i < res.size(); i++) {
      for (int j = 0; j < res[0].size(); j++) {
        res[i][j] += left[i][j];
      }
    }
    return res;
  }

  Matrix<T> operator*(T c) {
    Matrix<T> res = *this;
    for (int i = 0; i < res.size(); i++) {
      for (int j = 0; j < res[0].size(); j++) {
        res[i][j] *= c;
      }
    }
    return res;
  }

  vector<T>& operator[](int n) { return value[n]; }

  size_t size() { return value.size(); }

  Matrix<T> operator^(long long n) {
    Matrix<T> a = *this;
    Matrix<T> res(a.size(), a.size(), init);
    for (int i = 0; i < a.size(); i++) {
      res[i][i] = 1;
    }

    while (n > 0) {
      if (n & 1) res = res * a;
      a = a * a;
      n >>= 1;
    }
    return res;
  }
};

int R,C;
i64 T;

int sx,sy;
int gx,gy;

int fie[10][10];

int main(){
  cin >> R >> C >> T;
  cin >> sy >> sx;
  cin >> gy >> gx;
  rep(i,0,R - 1){
    string s;
    cin >> s;
    rep(j,0,C - 1){
      fie[i][j] = s[j] == '.';
    }
  }

  vector<vector<double>> m(100,vector<double>(100,0));

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

  rep(i,1,R - 2){
    rep(j,1,C - 2){
      if(fie[i][j] == 0) continue;
      int cnt = 0;
      cnt += fie[i + 1][j];
      cnt += fie[i - 1][j];
      cnt += fie[i][j + 1];
      cnt += fie[i][j - 1];

      if(cnt == 0){
        m[i * 10 + j][i * 10 + j] = 1;
      }
      else{
        for(int d = 0;d < 4;d++){
          if(fie[i + dx[d]][j + dy[d]] == 0) continue;
          m[(i + dx[d]) * 10 + (j + dy[d])][i * 10 + j] = 1.0 / cnt;
        }
      }
    }
  }

  Matrix<double> m2(100,1,0);
  m2[sy * 10 + sx][0] = 1;

  cout << fixed << setprecision(10);
  cout << ((Matrix<double>(m,0) ^ T) * m2)[gy * 10 + gx][0] << endl;
}
0