第二回 アルゴリズム実技検定 H - 1-9 Grid 解説

問題

問題文は本家サイトにあります：第二回 アルゴリズム実技検定 H - 1-9 Grid

問題概要

縦 $N$ マス、横 $M$ マスのマス目があり、各マスには '1' から '9' までの数字か 'S' か 'G' のどれかが書かれています。 'S', 'G' の書かれたマスはそれぞれ1つずつあります。

今、 'S' から出発して、隣り合う上下左右のマスをたどって 'G' に移動します。このとき、移動したときに踏んだ数字を並べたとき、（連続とは限らない）部分列をとると '1' から '9' までがこの順番で現れるように移動することとします。このような移動のうち、最小の移動回数を答えなさい。そのような移動がない場合は '-1' と答えなさい。

ただし、同じマスは複数回通ってよく、 'S' や 'G' の書かれたマスを途中で通過しても構いません。

制約

$1\leqq N, M \leqq 50$

解説

リンク先にある例で考えてみます。S と 5 の区別がつきにくいので、アルファベットは小文字で表記します。

1s23
4567
89g1

この場合、's'から左へいき、そのあと右端まで行くことで、 's1s23' とたどることになります。左端に戻って2行目を左端から右端まで行けば、 '32s14567' とたどることになります。また左端に戻って3行目を移動すれば、 '765489g' となります。こうして、
　s1s232s1456765489g
と数字を踏むことになり、'1' から '9' までがこの順番で現れるような部分列があることがわかります。これ以上短く移動できないので、17回が答えになります。

入力例2を見てもわかるとおり、先に大きい数字を踏んでしまっても構いません。同じマスを何度通ってもいいので、選べる経路の自由度が高いですね。

'1' から '9' までをいきなり考えるのは大変なので、S⇒1⇒2⇒G という簡単な例で考えることにしましょう。

一番思いつきやすい解法は、「まず一番近い1へ行き、次に一番近い2へ行き、Gに行く」という方法かもしれません。しかしこれは正しくありません。例えば、次のような場合にダメなことがわかります。

21s212
22222g

スタートのすぐ左に1がありますね。しかし、目先の1へ飛びつくとGから遠ざかってしまいます。最短は右の1へ行くルートです。

同様に、ゴールから一番近い2、そこから一番近い1、とたどっていくことも正しい解法ではありません。先ほどの例を逆にすればわかります。

12g121
11111s

このことからわかるのは、「S と 1 との距離だけ」や「G と 2 との距離だけ」を考えてもダメだということです。ある部分だけを抜き出して考えると、考えていない箇所で思わぬロスが発生していることがあるからです。

ただ、そうはいっても、1の書かれたマスへの最小移動回数は変わらないはずです。これは確定です。

      　　1への最小移動回数
21s212　　.1s.2.
22222g　　.....g

左の1へは1回の移動、右の1へは2回の移動で行けます。条件にあう移動を行うには、次に2へ移動しないといけません。今の場合、2の書かれた各マスへの最小移動回数もわかります。左の1か右の1からの移動距離はすぐにわかるので、近い方を選べばいいですね。

      　　2への最小移動回数
21s212　　2.s3.3
22222g　　32343g

あとはゴールへいくだけです。2の書かれた各マスへの最小移動回数がわかっているので簡単にわかります。ゴールのすぐ左のマスかゴールの上のマスから移動すればいいので、4回の移動だとわかります。

なお、2からゴールへの移動を考える際、スタートから1への移動や、1から2への移動は再度考える必要がない点に注意しましょう。2と書かれた各マスへの最小移動回数がわかればそれだけでOKです。

このように、1の書かれた各マスへの最小移動回数を求め、2の書かれた各マスへの最小移動回数を求め、… と繰り返していけば、'S' から 'G' への最小移動回数が求められます。それぞれの数字への最小移動回数を求めているから、これより少ない回数で移動することができないことがわかります。

$k$ の書かれた各マスへの最小移動回数は、 $k-1$ の書かれた各マスへの最小移動回数がわかれば求められます。 $k-1$ より小さな数が書かれたマスをどのようにたどってきたかは考えなくてもかまいません。つまり、いわゆる、動的計画法によって求めることができます。各マスから各マスへの最短距離を考えるので、計算量は $O(N^2M^2)$ となりますが、今の制約では間に合います。

以上を踏まえると、C++では以下のようにして書くことができます。コードの下に、コードの説明が続きます。

#include <iostream>
#include <vector>
using namespace std;

int main() {

  int N, M; cin >> N >> M;
  int gi, gj;
  vector<vector<int>> cells(N, vector<int>(M, 0));
  vector<vector<int>> dp(N, vector<int>(M, 1e9));

  for (int i = 0; i < N; i++) {
    string S; cin >> S;
    for (int j = 0; j < M; j++) {
      if (S[j] == 'S') {
        dp[i][j] = 0;
      } else if (S[j] == 'G') {
        cells[i][j] = 10;
        gi = i, gj = j;
      } else {
        cells[i][j] = S[j] - '0';
      }
    }
  }

  for (int k = 1; k <= 10; k++) {
    for (int i1 = 0; i1 < N; i1++) {
      for (int j1 = 0; j1 < M; j1++) {
        if (cells[i1][j1] != k) continue;

        for (int i2 = 0; i2 < N; i2++) {
          for (int j2 = 0; j2 < M; j2++) {
            if (cells[i2][j2] != k - 1) continue;

            int temp = dp[i2][j2] + abs(i1 - i2) + abs(j1 - j2);
            dp[i1][j1] = min(dp[i1][j1], temp);
          }
        }
      }
    }
  }

  int ans = dp[gi][gj];
  if (ans == 1e9) ans = -1;
  cout << ans << '\\n';
  return 0;
}

前半は、条件の取得です。 cells には、マスの状態を入れています。S は 0 に、G は 10 に変換しています。 dp には、条件通りに移動したときの、そのマスへの最小移動回数を入れることにします。大きな数を初期値として入れておき、S に対応する箇所には 0 を入れておきます。Sには 0回でたどりつけるからです。また、 G の場所を gi, gj に格納しておきます。

後半では、各マスへの最小移動回数を計算しています。 k の書かれたマス (i1, j1) への最小移動回数を考えます。これは、 k - 1 の書かれたそれぞれのマス (i2, j2) からの移動を考えればいいですね。2つのマスの間はどのマスを通って移動してもいいので、マス (i2, j2) からマス (i1, j1) への移動回数は abs(i1 - i2) + abs(j1 - j2) で求められます。なので、dp[i1][ji] は、

dp[i2][j2] + abs(i1 - i2) + abs(j1 - j2) の中で一番小さいもの

で求められることになります。

こうして、 dp[gi][gj] が答えになります。もし、1から9までのどれかの数字が欠けていると、この値は初めに設定した大きい値のままなので、-1 に変えます。答えを出力しておしまいです。