競技プログラミング日記

主に AtCoder の記事です

第二回 アルゴリズム実技検定 H問題

 

第二回 アルゴリズム実技検定 H問題

S,G のマスには 0,10 が書かれていると考える． dp_{h,w} := (Sのマス)から(h,w)への経路であって，0,1,\cdots, a_{h,w} を，この順に含むもの全体の中での\ min cost とする．

前処理として，
pv_{i} := iが書かれているマス全体
を求めておく． 遷移は
for \ (ch, cw) \in pv_{cu} : 今のマス
for \ (nh, cw) \in pv_{ne} : 次のマス
に対して全探索すればよい． 2マス間の距離はマンハッタン距離．

使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"

ll dp[55][55];

int main() {
  ll h,w; cin >> h >> w;
  vector<string> s(h);

  rep(i,h){
    cin >> s[i];
  }

  vector<vector<pll>> pv(11);
  rep(i,h) rep(j,w){
    if(s[i][j] == 'S') pv[0].emplace_back(i,j);
    else if(s[i][j] == 'G') pv[10].emplace_back(i,j);
    else pv[s[i][j]-'0'].emplace_back(i,j);
  }

  auto f = [&](ll x, ll y, ll s, ll t) -> ll {
    return abs(x-s) + abs(y-t);
  };


  rep(i,h) rep(j,w) dp[i][j] = INFL;
  auto [h0, w0] = pv[0].front();
  dp[h0][w0] = 0;
  rep(i,10){
    for(auto [ch,cw]: pv[i]){
      for(auto [nh,nw]: pv[i+1]){
        chmin(dp[nh][nw], dp[ch][cw] + f(ch,cw, nh,nw));
      }
    }
  }
  auto [h1, w1] = pv[10].front();
  ll *po = &(dp[h1][w1]);
  if(*po >= INFL) *po = -1;
  cout << *po << endl;

  return 0;
}