2019年09月26日02時52分40秒に更新されたバージョンを表示しています.
最新のページはこちらをご覧ください.
Mujin Programming Challenge 2018
問題文
省略
省略
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: 2024年04月29日06時02分52秒
Last modified: 2019年09月26日02時52分40秒 (by laycrs)
Tags: Competitive_Programming_Incomplete AtCoder
トップページに戻る
Logged in as: unknown user (not login)