AOJ2157 Dial Lock

問題リンク Dial Lock

• 概要

K桁のダイヤルロックがある。範囲[s, t](0 <= s <= t < K)を選んで、この範囲のダイヤルを同時に任意の位置まで回すことができる。初期配置Sから、ロックが外れる配置Tにするために、ダイヤルを回す回数を最小化せよ。
1 <= K <= 10

• 解法

DPの方針で考えていましたが、DFSで解きました。
ダイヤルの左側の数字sから考えていき、S_sとT_sの数字が違えば、数字を合わせるように回します。このとき、回す範囲の右端t (s <= t < K)を全て試します。sについて考えたらs+1について再帰的に考えます。ざっと、O(K!)かかりますが、意外と間に合ってくれます。

• ソース

import java.util.Scanner;

//Dial Lock
public class AOJ2157 {

	int n, res;
	int[] now, ans;
	
	void f(int k, int cnt){
		if(res<=cnt)return;
		if(k==n){
			res = cnt; return;
		}
		if(now[k]==ans[k])f(k+1, cnt);
		else{
			int dif = ans[k]-now[k];
			if(dif<0)dif+=10;
			for(int j=k;j<n;j++){
				now[j] = (now[j]+dif)%10;
				f(k+1, cnt+1);
			}
			for(int j=k;j<n;j++)now[j] = (now[j]+10-dif)%10;
		}
	}
	
	void run(){
		Scanner sc = new Scanner(System.in);
		for(;;){
			n = sc.nextInt();
			if(n==0)break;
			now = new int[n];
			ans = new int[n];
			char[] s = sc.next().toCharArray();
			for(int i=0;i<n;i++)now[i]=s[i]-'0';
			s = sc.next().toCharArray();
			for(int i=0;i<n;i++)ans[i]=s[i]-'0';
			res = n;
			f(0, 0);
			System.out.println(res);
		}
	}
	
	public static void main(String[] args) {
		new AOJ2157().run();
	}
}