結果

問題 No.659 徘徊迷路
ユーザー たこしたこし
提出日時 2018-11-01 21:54:27
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 89 ms / 2,000 ms
コード長 3,163 bytes
コンパイル時間 2,303 ms
コンパイル使用メモリ 213,660 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-11-20 06:24:33
合計ジャッジ時間 3,863 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;

#define INF 100000000
#define YJ 1145141919
#define INF_INT_MAX 2147483647
#define INF_LL 9223372036854775
#define INF_LL_MAX 9223372036854775807
#define EPS 1e-10
#define MOD 10000
#define Pi acos(-1)
#define LL long long
#define ULL unsigned long long
#define LD long double

#define int long long

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(a)  begin((a)), end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())

template <typename T>
class Matrix {
public:
  Matrix(int r, int c) {
    mat.clear();
    for(int i = 0; i < r; i++) {
      mat.push_back(vector<T>());
      mat[i].resize(c);
    }
  }

  vector<T>& operator[] (int r) {
    return mat[r];
  }

  void print() const {
    for(int i = 0; i < mat.size(); i++) {
      for(int j = 0; j < mat[i].size(); j++) {
        cerr << mat[i][j] << " ";
      }
      cerr << endl;
    }
  }

  unsigned int getR() const {
    return mat.size();
  }

  unsigned int getC() const {
    return mat[0].size();
  }

  Matrix operator + (Matrix& matrix) {
    Matrix<T> ret(this->getR(), this->getC());
    for(int r = 0; r < matrix.getR(); r++) {
      for(int c = 0; c < matrix.getC(); c++) {
        ret[r][c] = (*this)[r][c] + matrix[r][c];
      }
    }
    return ret;
  }

  void operator += (Matrix& matrix) {
    for(int r = 0; r < matrix.getR(); r++) {
      for(int c = 0; c < matrix.getC(); c++) {
        (*this)[r][c] += matrix[r][c];
      }
    }
  }

  Matrix operator * (Matrix& matrix) {
    Matrix<T> ret(this->getR(), matrix.getC());
    for(int r = 0; r < getR(); r++) {
      for(int c = 0; c < matrix.getC(); c++) {
        for(int rr = 0; rr < matrix.getR(); rr++) {
          ret[r][c] += (*this)[r][rr] * matrix[rr][c];
        }
      }
    }
    return ret;
  }

  void operator *= (Matrix& matrix) {
    (*this) = (*this) * matrix;
  }

private:
  vector<vector<T>> mat;
};

const int MAX_R = 10;
const int MAX_C = 10;
int R,C,T;
int Sy,Sx;
int Gy,Gx;
char B[MAX_R][MAX_C];
int dr[] = {1,-1,0,0};
int dc[] = {0,0,1,-1};

signed main()
{
  cin >> R >> C >> T;
  cin >> Sy >> Sx;
  cin >> Gy >> Gx;
  REP(r,R) {
    REP(c,C) {
      cin >> B[r][c];
    }
  }

  Matrix<long double> startMat(1,R*C);
  startMat[0][Sy*C + Sx] = 1.0;

  Matrix<long double> moveMatrix(R*C, R*C);
  REP(r,R) {
    REP(c,C) {
      if(B[r][c] == '#') {
        continue;
      }

      double k = 0;
      REP(d,4) {
        int nr = r + dr[d];
        int nc = c + dc[d];
        if(B[nr][nc] != '#') {
          k++;
        }
      }

      if(k != 0) {
        REP(d,4) {
          int nr = r + dr[d];
          int nc = c + dc[d];
          if(B[nr][nc] != '#') {
            moveMatrix[r*C+c][nr*C+nc] = 1.0/k;
          }
        }
      } else {
        moveMatrix[r*C+c][r*C+c] = 1.0;
      }
    }
  }

  Matrix<long double> tmpMatrix(R*C, R*C);
  tmpMatrix = moveMatrix;
  
  while(T) {
    if(T&1) {
      startMat *= tmpMatrix;
    }
    T >>= 1;
    tmpMatrix *= tmpMatrix;
  }

  printf("%.15Lf\n", startMat[0][Gy*C+Gx]);

  return 0;
}
0