2157 - Dial Lock

AOJ
問題

0~9の数字が書かれたk個のダイアルがある鍵を考える。
連続するダイアルを同じ方向に同じ数だけ回す動作を１手とする。
このときダイアルを初期状態sから目標状態tにする手数を求めよ。

制約

1 <= k <= 10

解法

まず回す順番は関係がないので左から数字を合わせていくことをイメージする。
このとき、現在のダイアルを目標状態以外する意味はないので、目標状態にする分だけ回す。
ただし、どれだけの数のダイアルを一緒に回せばいいか分からないので、それは全部試す。
枝刈りDFSで解いたけどBFSで良かったと思う。

ソース
int k;
string t;
int mi;
int solve(const string &ts, int now, int c) {
  if (c >= mi) return c;        // 枝刈り
  if (now == k) {
    mi = min(mi, c);
    return c;
  }
  int d = t[now]-ts[now];
  if (d == 0) return solve(ts, now+1, c);
  int res = INF;
  for (int i=now; i<k; ++i) {
    string s = ts;
    for (int j=now; j<=i; ++j) {
      s[j] = (s[j]-'0'+d+10)%10 + '0';
    }
    res = min(res, solve(s, now+1, c+1));
  }
  return res;
}

int main() {
  while(cin>>k, k) {
    string s;
    cin >> s >> t;
    mi = INF;
    cout << solve(s,0,0) << endl;
  }
}