Mujin Programming Challenge 2018 E問題 - 迷路

Source

Mujin Programming Challenge 2018
問題文

問題概要

省略

解法

省略

cLayversion 20190925-1)のコード

C++に変換後のコードはこちら

int X, Y, K;
char S[1001][1002];
char T[100003];

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

{
  int i, j, k, kk, d;
  int sx, sy, nx, ny;
  int xx1, yy1, xx2, yy2;
  ll cost, ncost, res;
  DijkstraHeap<ll> hp;
  
  rd(X,Y,K,T,S(X));

  rep(i,X) rep(j,Y){
    if(S[i][j]=='S') xx1 = i, yy1 = j;
    if(S[i][j]=='G') xx2 = i, yy2 = j;
  }

  rep(i,4) rep(k,K) go[i][k] = -1;
  rep(k,K){
    if(T[k]=='U') go[0][k] = 1;
    if(T[k]=='R') go[1][k] = 1;
    if(T[k]=='D') go[2][k] = 1;
    if(T[k]=='L') go[3][k] = 1;
  }
  rep(j,2) rep(i,4) rrep(k,K) if(go[i][k]==-1){
    kk = k+1;
    if(kk==K) kk = 0;
    if(go[i][kk]!=-1) go[i][k] = go[i][kk] + 1;
  }

  hp.malloc(X*Y);
  hp.init(X*Y);

  hp.change(xx1*Y+yy1, 0);
  while(hp.size){
    k = hp.pop();
    sx = k / Y;
    sy = k % Y;
    cost = hp.val[k];
    
    rep(d,4){
      nx = sx + dx[d];
      ny = sy + dy[d];
      if(nx < 0 || ny < 0 || nx >= X || ny >= Y || S[nx][ny]=='#') continue;
      if(go[d][cost%K]==-1) continue;
      ncost = cost + go[d][cost%K];
      hp.change(nx*Y+ny, ncost);
    }
  }

  if(hp.visited[xx2*Y+yy2]) res = hp.val[xx2*Y+yy2]; else res = -1;
  wt(res);
}

Current time: 2021年09月28日22時42分50秒
Last modified: 2019年09月26日02時52分40秒 (by laycrs)
Tags: Competitive_Programming_Incomplete AtCoder
トップページに戻る

Logged in as: unknown user (not login)

ログイン: