AtCoder Regular Contest #019 C問題 - 最後の森

Source

AtCoder Regular Contest #019
問題文

問題概要

$R$ 行 $C$ 列の盤面が与えられる．
上下左右に移動できる．
スタート地点，祠，魔王の城がそれぞれ1セルずつあって，スタート地点から祠に行き，その後，魔王の城に行きたい．
各セルは，移動できる，移動できない，敵がいるの $3$ 種類で，敵がいるセルは敵を倒せばその後はずっと自由に移動できるようになる．
ただし，敵を倒すのは合計で $K$ 回以下でなくてはいけない．
スタート地点，祠，魔王の城は移動できるセル．
最小移動距離を求める問題．辿りつけないならそれを指摘する．

解法

スタート地点，祠，魔王の城の各セルを始点として，全てのセルまでの $i$ マス以下の敵のマスを通る場合の最短移動距離（$i=0,1,2,\ldots$）をBFSなどで求めておく．
スタート地点→祠，と，祠→魔王の城の共通で通るセルは，祠→分岐点のセル，となる（することができる）．
そこで，分岐点を全部試す．
スタート地点→分岐点，分岐点→祠，祠→分岐点，分岐点→魔王の城と移動することになり，各パートにどれだけ敵を割り振るかを全部試す．
どれだけの敵を割り振るかを決めたら，前計算していた結果を用いれば，$O(1)$ で最短移動距離が求まる．
分岐点のセルの敵を重複して数えないように注意する．
合計で時間計算量 $O(RCK^2)$ 程度．

C++によるスパゲッティなソースコード

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)

void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
int reader(char c[]){int i,s=0;for(;;){mygc(i);if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t') break;}c[s++]=i;for(;;){mygc(i);if(i==' '||i=='\n'||i=='\r'||i=='\t') break;c[s++]=i;}return s;}
void writer(int x, char c){int i,sz=0,m=0;char buf[10];if(x<0)m=1,x=-x;while(x)buf[sz++]=x%10,x/=10;if(!sz)buf[sz++]=0;if(m)mypc('-');while(sz--)mypc(buf[sz]+'0');mypc(c);}

#define INF 100000000

int x, y, z;
char in[51][51];
int dist[51][51][111];

void get_dist(int sx, int sy){
  int i, j, k, d, c, val;
  int ni, nj, nk;
  static int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, 1, -1};
  static int q[450000], q_st, q_size;
  
  rep(i,x) rep(j,y) rep(k,z+11) dist[i][j][k] = INF;
  
  q[0] = (sx * y + sy) * (z+11) + 0;
  q_st = 0;
  q_size = 1;
  dist[sx][sy][0] = 0;
  
  while(q_size){
    val = q[q_st++]; q_size--;
    k = val % (z+11); val /= (z+11);
    j = val % y;      val /= y;
    i = val;
    c = dist[i][j][k];
    
    rep(d,4){
      ni = i + dx[d];
      nj = j + dy[d];
      if(ni < 0 || nj < 0 || ni >= x || nj >= y || in[ni][nj]=='T') continue;
      nk = k;
      if(in[ni][nj]=='E') nk++;
      if(nk > z+10) continue;
      if(dist[ni][nj][nk]==INF){
        dist[ni][nj][nk] = c+1;
        q[q_st+q_size++] = (ni * y + nj) * (z+11) + nk;
      }
    }
  }
  
  rep(i,x) rep(j,y){
    REP(k,1,z+11) if(dist[i][j][k] > dist[i][j][k-1]) dist[i][j][k] = dist[i][j][k-1];
  }
}

int main(){
  int i,j,k,l,m,n;
  
  static int dist1[51][51][111];
  static int dist2[51][51][111];
  static int dist3[51][51][111];
  
  int sx, sy, mx, my, ex, ey;
  int res = INF, tmp;

  reader(&x);
  reader(&y);
  reader(&z);
  rep(i,x) reader(in[i]);
 
  rep(i,x) rep(j,y){
    if(in[i][j] == 'S'){ in[i][j]='.'; sx = i; sy = j; continue; }
    if(in[i][j] == 'C'){ in[i][j]='.'; mx = i; my = j; continue; }
    if(in[i][j] == 'G'){ in[i][j]='.'; ex = i; ey = j; continue; }
  }
  
  get_dist(sx, sy);
  rep(i,x) rep(j,y) rep(k,z+11) dist1[i][j][k] = dist[i][j][k];
  get_dist(mx, my);
  rep(i,x) rep(j,y) rep(k,z+11) dist2[i][j][k] = dist[i][j][k];
  get_dist(ex, ey);
  rep(i,x) rep(j,y) rep(k,z+11) dist3[i][j][k] = dist[i][j][k];
  
  rep(i,x) rep(j,y){
    rep(k,z+1) rep(l,z+1-k){
      m = z - k - l;
      if(in[i][j]=='E') m+=2;
      tmp = dist1[i][j][k] + 2*dist2[i][j][m] + dist3[i][j][l];
      if(res > tmp) res = tmp;
    }
  }
  
  if(res == INF) res = -1;
  writer(res, '\n');
  
  return 0;
}

Current time: 2024年04月24日08時27分56秒
Last modified: 2014年04月13日06時26分53秒 (by laycrs)
Tags: Competitive_Programming AtCoder AtCoder_Regular_Contest ARC019 ARC_C
トップページに戻る

Logged in as: unknown user (not login)

ログイン：