Algoogle

Algorithm for Programming Contest

AOJ 2157 Dial Lock

Category: AOJ Tag: bfs, dijkstra

Dial Lock

問題概要


数列の連続している区間に同じ数字を足すことでsからtにしたい.
このとき区間に値を加える回数の最小を求めよ.

解法


Dijkstra(BFS)する.
数列の左から順にダイヤルをあわせる.
合ってない一番左のダイヤルにあわせるように加える値を決めたら, そこから一番右端までの区間にその値をたしていき, 毎回できる数列をqueueにプッシュすれば良い.
これで計算量はO(K!)程度になる.

コード


(2157.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
using namespace std;
#define repi(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,a) repi(i,0,a)
int N;
string s, t;
map<string,int> dist;

int solve(){
    dist.clear();
    queue<string> que;
    que.push(s);
    dist[s] = 0;
    while(!que.empty()){
        string v = que.front(); que.pop();
        int d = dist[v];
        if(v == t) return d;
        int nl = 0;
        while(nl < N and v[nl] == t[nl]) nl++;
        int c = (t[nl]-v[nl]+10)%10;
        repi(l,nl,N) {
            v[l] = (v[l]+c-'0') %10 + '0';
            if(dist.find(v) == end(dist)) {
                dist[v] = d+1;
                que.push(v);
            }
        }
    }
}

bool input(){
    cin >> N;
    if(!N) return 0;
    cin >> s >> t;
    return 1;
}

signed main(){
    while(input()) cout << solve() << endl;
    return 0;
}

Comments