Submission #14502993


Source Code Expand

Copy
#include<bits/stdc++.h>
#define rep(i, x) for (ll i = 0; i < (x); i++)

using namespace std;
typedef long long int ll;
template<typename T>
using reversed_priority_queue = \
    std::priority_queue<T, std::vector<T>, std::greater<T> >;

const ll INF = 1e16;
ll Y, X, K;
ll sx, sy, gx, gy;
vector<vector<vector<ll>>> dp; // dp[y][x][dir]
vector<string> s;

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

int main(void) {
  // input
  cin >> Y >> X >> K;
  cin >> sy >> sx >> gy >> gx;
  sx--, sy--, gx--, gy--;
  s.resize(Y);
  rep(y, Y)
    cin >> s[y];

  // init dp
  dp.resize(Y, vector<vector<ll>>(X, vector<ll>(4, INF)));

  // dijkstra
  typedef tuple<ll, ll, ll, ll> T;
  reversed_priority_queue<T> q; // {cost, y, x, dir}
  rep(dir, 4)
    q.emplace(0, sy, sx, dir);
  while (!q.empty()) {
    auto [cost, y, x, dir] = q.top();
    q.pop();
    // printf("cost=%lld y=%lld x=%lld dir=%lld\n", cost ,y, x, dir);
    if (y < 0 || y >= Y || x < 0 || x >= X) continue;
    if (dir < 0 || dir >= 4) continue;
    if (dp[y][x][dir] <= cost) continue;
    if (s[y][x] == '@') continue;
    dp[y][x][dir] = cost;
    // 向きを変える
    rep(ndir, 4) {
      q.emplace(((cost + K - 1) / K) * K, y, x, ndir);
    }
    // その方向に進む
    ll nx = x + dx[dir], ny = y + dy[dir];
    q.emplace(cost + 1, ny, nx, dir);
  }
  ll ans = INF;
  rep(dir, 4) {
    if (dp[gy][gx][dir] == INF)
      continue;
    auto cost = (dp[gy][gx][dir] + K - 1) / K;
    ans = min(ans, cost);
  }

  if (ans == INF)
    ans = -1;
  cout << ans << endl;
  return 0;
}

Submission Info

Submission Time
Task F - Pond Skater
User bobuhiro11
Language C++ (GCC 9.2.1)
Score 600
Code Size 1629 Byte
Status
Exec Time 2741 ms
Memory 144952 KB

Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 Sample_01.txt, Sample_02.txt, Sample_03.txt
All 600 / 600 Sample_01.txt, Sample_02.txt, Sample_03.txt, killer_01.txt, killer_02.txt, killer_03.txt, killer_04.txt, killer_05.txt, ng_large_01.txt, ng_large_02.txt, ng_large_03.txt, ng_small_01.txt, ng_small_02.txt, ng_small_03.txt, path_01.txt, path_02.txt, path_03.txt, path_04.txt, path_05.txt, rand_1000_01.txt, rand_1000_02.txt, rand_1000_03.txt, rand_20_01.txt, rand_20_02.txt, rand_20_03.txt, rand_300_01.txt, rand_300_02.txt, rand_300_03.txt, rand_small_01.txt, rand_small_02.txt, rand_small_03.txt, superkiller_01.txt
Case Name Status Exec Time Memory
Sample_01.txt 7 ms 3564 KB
Sample_02.txt 3 ms 3560 KB
Sample_03.txt 2 ms 3604 KB
killer_01.txt 2741 ms 108240 KB
killer_02.txt 2721 ms 108304 KB
killer_03.txt 2078 ms 79604 KB
killer_04.txt 2387 ms 83788 KB
killer_05.txt 2180 ms 79564 KB
ng_large_01.txt 97 ms 68828 KB
ng_large_02.txt 100 ms 67852 KB
ng_large_03.txt 93 ms 63632 KB
ng_small_01.txt 3 ms 3484 KB
ng_small_02.txt 3 ms 3512 KB
ng_small_03.txt 4 ms 3484 KB
path_01.txt 174 ms 144892 KB
path_02.txt 177 ms 144952 KB
path_03.txt 575 ms 144780 KB
path_04.txt 380 ms 144776 KB
path_05.txt 908 ms 144852 KB
rand_1000_01.txt 2597 ms 69160 KB
rand_1000_02.txt 2720 ms 71440 KB
rand_1000_03.txt 2458 ms 64588 KB
rand_20_01.txt 1727 ms 68588 KB
rand_20_02.txt 2533 ms 74128 KB
rand_20_03.txt 2215 ms 70996 KB
rand_300_01.txt 2416 ms 66468 KB
rand_300_02.txt 2628 ms 70812 KB
rand_300_03.txt 2537 ms 68796 KB
rand_small_01.txt 2 ms 3616 KB
rand_small_02.txt 2 ms 3520 KB
rand_small_03.txt 3 ms 3604 KB
superkiller_01.txt 439 ms 75764 KB