結果

問題 No.659 徘徊迷路
コンテスト
ユーザー letrangerjp
提出日時 2018-03-03 19:10:35
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 4 ms / 2,000 ms
コード長 1,752 bytes
コンパイル時間 140 ms
コンパイル使用メモリ 31,616 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-04 01:38:22
合計ジャッジ時間 826 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int R, C, T;
int Sy, Sx, Gy, Gx;
double dp[10][10] = {0}, next_dp[10][10] = {0};
char Board[10][11];
long flags[10][10] = {0};
const int DIRS[][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
const int BITS_COUNT[] = {
  0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
};

int main(void) {
  scanf("%d %d %d\n", &R, &C, &T);
  scanf("%d %d\n", &Sy, &Sx);
  scanf("%d %d\n", &Gy, &Gx);
  for (int y = 0; y < R; ++y) {
    scanf("%s\n", Board[y]);
  }

  for (int y = 1; y < R-1; ++y) {
    for (int x = 1; x < C-1; ++x) {
      long flg  = 0;
      for (int d = 0; d < 4; ++d) {
        int dy = DIRS[d][0];
        int dx = DIRS[d][1];
        if (Board[y+dy][x+dx] == '#')
          continue;
        flg |= 1 << d;
      }
      flags[y][x] = flg;
    }
  }

  dp[Sy][Sx] = 1.0;
  int times = T > 5000 ? (5000 | T%2) : T;

  for (int i = 0; i < times; ++i) {
    for (int y = 1; y < R-1; ++y) {
      for (int x = 1; x < C-1; ++x) {
        if (Board[y][x] == '#')
          continue;
        int dir_count = BITS_COUNT[flags[y][x]];
        if (dir_count == 0) {
          next_dp[y][x] += dp[y][x];
          continue;
        }
        for (int d = 0; d < 4; ++d) {
          if (flags[y][x] & (1 << d) == 0)
            continue;
          int dy = DIRS[d][0];
          int dx = DIRS[d][1];
          next_dp[y+dy][x+dx] += dp[y][x] / (double)dir_count;
        }
      }
    }
    memcpy(dp, next_dp, sizeof(next_dp));
    memset(next_dp, 0, sizeof(next_dp));
    // for (int i = 0; i < 10; ++i) {
    //   for (int j = 0; j < 10; ++j) {
    //     printf("%f ", dp[i][j]);
    //     // printf("%d ", flags[i][j]);
    //   }
    //   puts("");
    // }
  }
  printf("%f\n", dp[Gy][Gx]);
}
0