解題區/解題區 - UVa

UVa 1089 - Suffix-Replacement Grammars

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

限定修改後綴，請問至少需要幾次轉換能從起始字串轉換到目標字串。

Sample Input

1
2
3
4
5
6
7
8
9
10
AA BB 4 
A B 
AB BA 
AA CC 
CC BB 
A B 3 
A C 
B C 
c B 
.

Sample Output

1
2
Case 1: 2 
Case 2: No solution

Solution

一開始用 Bfs 下去搜索，發現狀態會是 O(2^len)，這麼轉換就不太行。

將語法中單詞、起始字串、目標字串的後綴按照長度分層，將從長度為 1 的轉換開始，依序完成到 len。將後綴建成一張圖，套用 floyd algorithm 找最少轉換次數。

1
2
A -> B, cost 1
Aaaaaa -> Abbbbb, cost aaaaa -> bbbbb

考慮長度 i 的轉換時，有可能存在給定的語法可以直接進行轉換，或者存在在長度 (i - 1) 時的最少轉換次數。

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include <stdio.h> 
#include <iostream>
#include <map>
#include <vector>
#include <set>
#include <algorithm>
#include <assert.h>
using namespace std;
const int MAXS = 25;
const int MAXR = 105;
const int MAXN = 512;
map<string, int> Rmap[MAXS];
vector<string> Rvec[MAXS];
void addNode(string s) {
    int len = s.length(), label;
    if (!Rmap[len].count(s)) {
        label = Rmap[len].size();
        Rmap[len][s] = label;
        Rvec[len].push_back(s);
        assert(label < MAXN);
    }
}
// floyd
long long dist[MAXN][MAXN], preDist[MAXN][MAXN];
const long long INF = 1LL<<61;
int main() {
    string A, B, x, y;
    int M, N, cases = 0;
    while (cin >> A >> B >> M) {
        if (A == ".")
            return 0;
        set< pair<string, string> > rules;
        for (int i = 0; i < MAXS; i++)
            Rmap[i].clear(), Rvec[i].clear();
            
        for (int i = 0; i < M; i++) {
            cin >> x >> y;
            rules.insert(make_pair(x, y));
            for (int j = 0; j < x.length(); j++) {
                string s1 = x.substr(j), s2 = y.substr(j);
                addNode(s1), addNode(s2);
            }
        }
        
        N = A.length();
        for (int i = 0; i < N; i++) {
            string s1 = A.substr(i), s2 = B.substr(i);
            addNode(s1), addNode(s2);
        }
        
        for (int p = 1; p <= N; p++) {
            int n = Rmap[p].size();
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (i == j)	
                        dist[i][j] = 0;
                    else {
                        dist[i][j] = INF;
                        if (rules.count(make_pair(Rvec[p][i], Rvec[p][j]))) {
                            dist[i][j] = min(dist[i][j], 1LL); // rule A -> B, cost 1
                        }
                        if (p > 1 && Rvec[p][i][0] == Rvec[p][j][0]) { // node Aaaaaa -> Abbbbb, cost aaaaa -> bbbbb
                            int pi = Rmap[p-1][Rvec[p][i].substr(1)];
                            int pj = Rmap[p-1][Rvec[p][j].substr(1)];
                            dist[i][j] = min(dist[i][j], preDist[pi][pj]);
                        }
                    }
                }
            }
            
            // floyd algorithm
            for (int k = 0; k < n; k++) 
                for (int i = 0; i < n; i++)
                    for (int j = 0; j < n; j++)
                        dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            
            // copy for next loop
            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++)
                    preDist[i][j] = dist[i][j];
        }
        
        int st = Rmap[N][A], ed = Rmap[N][B];
        long long d = dist[st][ed];
        
        printf("Case %d: ", ++cases);
        if (d >= INF)
            printf("No solution\n");
        else
            printf("%lld\n", d);
    }
    return 0;
}
/*
AAAAAAAAAAAAAAAAAAAA BBBBBBBBBBBBBBBBBBBB 20
ABBBBBBBBBBBBBBBBBBB BAAAAAAAAAAAAAAAAAAA
ABBBBBBBBBBBBBBBBBB  BAAAAAAAAAAAAAAAAAA 
ABBBBBBBBBBBBBBBBB   BAAAAAAAAAAAAAAAAA  
ABBBBBBBBBBBBBBBB    BAAAAAAAAAAAAAAAA   
ABBBBBBBBBBBBBBB     BAAAAAAAAAAAAAAA    
ABBBBBBBBBBBBBB      BAAAAAAAAAAAAAA     
ABBBBBBBBBBBBB       BAAAAAAAAAAAAA      
ABBBBBBBBBBBB        BAAAAAAAAAAAA       
ABBBBBBBBBBB         BAAAAAAAAAAA        
ABBBBBBBBBB          BAAAAAAAAAA         
ABBBBBBBBB           BAAAAAAAAA          
ABBBBBBBB            BAAAAAAAA           
ABBBBBBB             BAAAAAAA            
ABBBBBB              BAAAAAA             
ABBBBB               BAAAAA              
ABBBB                BAAAA               
ABBB                 BAAA                
ABB                  BAA                 
AB                   BA                  
A                    B   
*/