結果
問題 | No.659 徘徊迷路 |
ユーザー |
|
提出日時 | 2018-03-03 17:07:26 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 137 ms / 2,000 ms |
コード長 | 3,178 bytes |
コンパイル時間 | 792 ms |
コンパイル使用メモリ | 80,236 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-06-30 04:43:54 |
合計ジャッジ時間 | 2,908 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 12 |
ソースコード
#include <cstdio> #include <string> #include <iostream> #include <vector> #include <cmath> #include <cassert> using namespace std; #define MAX 1000001 typedef vector<long double> vec; typedef vector<vec> mat; char map[10][10]; int r, c, t, sx, sy, gx, gy; int ds[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; mat mul(mat &A, mat &B) { mat C(A.size(), vec(B[0].size())); for(int i=0; i<A.size(); i++) { for(int k=0; k<B.size(); k++) { for(int j=0; j<B[0].size(); j++) { C[i][j] = (C[i][j]+A[i][k]*B[k][j]); } //printf("i=%d, k=%d, C[i][k]=%f\n", i, k, C[i][k]); //assert(C[i][k]<=1); } } return C; } void printMat(mat &A) { int n = A.size(); int m = A[0].size(); printf("["); for(int i=0; i<n; i++) { printf("["); for(int j=0; j<m; j++) { printf("%f,", A[i][j]); } printf("];"); } printf("]\n"); } mat pow(mat A, long n) { mat B(A.size(), vec(A.size())); // printf("B %d %d\n", B.size(), B[0].size()); for(int i=0; i<A.size(); i++) { B[i][i] = 1; } while(n>0) { if(n&1) B = mul(B, A); A = mul(A, A); n >>= 1; } return B; } // memo aがおかしい double solve() { { int unko = 0; for(int k=0; k<4; k++) { int ny = sy+ds[k][0]; int nx = sx+ds[k][1]; if(0<=ny && ny < r && 0<=nx && nx < c && map[ny][nx] == '.') unko++; } //printf("unko=%d, sx=%d, gx=%d, sy=%d, gy=%d\n", unko, sx, gx, sy, gy); // if(unko==0 && sx==gx && sy==gy) return 1; if(unko==0) return 0; } mat A(101, vec(101)); for(int y=0; y<r; y++) { for(int x=0; x<c; x++) { A[y][x] = 0; } } //printMat(A); for(int y=0; y<r; y++) { for(int x=0; x<c; x++) { if(map[y][x]=='.') { int tmp = 0; for(int k=0; k<4; k++) { int ny = y+ds[k][0]; int nx = x+ds[k][1]; if(0<=ny && ny < r && 0<=nx && nx < c && map[ny][nx] == '.') tmp++; } // printf("y=%d, x=%d, cnt=%d\n", y, x, tmp); int current = c*y+x; if(tmp==0) A[current][current]=1; //printf("@@@@@\n"); //printf("y: %d, x: %d, tmp: %d\n", y, x, tmp); for(int k=0; k<4; k++) { int ny = y+ds[k][0]; int nx = x+ds[k][1]; if(0<=ny && ny < r && 0<=nx && nx < c && map[ny][nx] == '.') { int next = c*ny+nx; // printf("(%d, %d) -> (%d, %d) = %f\n", y, x, ny, nx, (double)1/(double)tmp); if(tmp==0) break; A[current][next] = (double)1/(double)tmp; //assert(A[current][next]<=1.0); //printf("A[c][n]=%f\n", A[current][next]); } } //printf("@@@@@\n"); } //if(y==0) printMat(A); } } // A = pow(A, t); // for(int y=0; y<r; y++) { // for(int x=0; x<c; x++) { // int current = y*r+x; // for(int k=0; k<4; k++) { // int ny = y+ds[k][0]; // int nx = x+ds[k][1]; // if(0<=ny && ny < r && 0<=nx && nx < c && map[ny][nx] == '.') { // int next = r*ny+nx; // printf("(%d, %d) -> (%d, %d) = %f\n", y, x, ny, nx, A[current][next]); // } // } // } // } //printMat(A); A = pow(A, t); return A[c*sy+sx][c*gy+gx]; } int main() { cin >> r >> c >> t >> sy >> sx >> gy >> gx; for(int i=0; i<r; i++) { scanf("%s", &map[i]); } cout << solve() << '\n'; return 0; }