aoj2157:Dial Lock

問題文

Dial Lock | Aizu Online Judge

解法

A[x]!=B[x]となるようなxの中で最小のものをとり、iとする。
i番目の桁より左は既に完成してるので、存在しないものとして考えても問題ない。
i番目の桁を合わせるために、少なくとも一度はi番目を含むような区間を変更しなくてはならない。
すなわち、少なくとも1度は区間[i,j](i<=j< N　|この記事では、0-indexedで考えます)に操作する必要があります。
もし区間[i,j]と区間[i,k](i<=j< k < N)に操作するとき、回す量を適当に調整すれば、
区間[i,j]と区間[j+1,k]への2つの操作で全く同じ効果を得ることができる。
よって、本質的には、i番目を左端とする操作は1度だけでいい。

上のような考え方を再帰的に適用して考えると、以下のような深さ優先探索をすればいい。

dfs(n):
・n==Nなら、0を返す。
・A[n]==B[n]ならdfs(n+1)を返す。
・区間[i,j]への変更を行い、dfs(n+1)+1を得る。これをi<=j< Nを満たすすべてのjについて試す。

dfs(0)を出力すればokです。

計算量は、O(K! * K)で、K<=10なのでたぶん通ります。

コード

#include<bits/stdc++.h>
using namespace std;

#define int long long
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define all(v) (v).begin(),(v).end()
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define pb push_back
#define fi first
#define se second
template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

int N;
int A[11],B[11];
int dfs(int n){
    if(n==N)return 0;
    if(A[n]==B[n])return dfs(n+1);

    int t=B[n]-A[n];
    if(t<0)t+=10;
    int ret=1001001001;
    for(int i=n+1;i<=N;i++){
        for(int j=n;j<i;j++)A[j]=(A[j]+t)%10;
        chmin(ret,dfs(n+1)+1);
        for(int j=n;j<i;j++)A[j]=(A[j]-t+10)%10;
    }
    return ret;
}

signed main(){
    while(cin>>N,N){
        string S,T;
        cin>>S>>T;
        rep(i,N){
            A[i]=S[i]-'0';
            B[i]=T[i]-'0';
        }
        cout<<dfs(0)<<endl;
    }
    return 0;
}