UVA 11198 Dancing Digits

uva bfs

用 bfs 把所有可能跑一次. 當中要用到 hash 去記綠試了那些可能性.
我面對 BFS 和 DFS 的問題時, 總是會覺得有其他方法. 到最後才試 bfs, 浪費了不少時間.

uva11198.cpp
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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#include <cstdio>
#include <cstring>
#include <cmath>
#include <map>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

const int len = 8;

const int LEFT = 0;
const int RIGHT = 1;

vector<int> inp;
map <int, bool> visited;
bool isprime[20];

void slave_prime() {

    memset(isprime, true, sizeof(isprime));

    isprime[0] = isprime[1] = false;
    for(int i = 4; i < 20; i+=2)
        isprime[i] = false;

    int limit = sqrt(20) + 1;
    for(int i = 3; i < limit; i+=2) {
        if(isprime[i]) {
            for(int j = i * 2; j < 20; j += i)
                isprime[j] = false;
        }
    }
}

int getOrd(vector<int> a) {
    int sum = 0;

    for(int i = 0; i < 8; ++i) {
        sum *= 10;
        sum += abs(a[i]);
    }
    return sum;
}

vector<int> dance(const vector<int>& v, int idxA, int idxB, int pos) {
    vector<int> newv(v);
    int i, counter = 0;
    int vb = newv[idxB];
    if(pos == LEFT) { // move B to A left
        if(idxA < idxB) {
            for(int i = idxB; i >= idxA + 1 ; --i) {
                newv[i] = newv[i - 1];
            }
            newv[idxA] = vb;
        } else {
            for(int i = idxB; i <= idxA - 1 ; ++i) {
                newv[i] = newv[i + 1];
            }
            newv[idxA - 1] = vb;
        }
    } else { // move B to A right
        if(idxA < idxB) {
            for(int i = idxB; i >= idxA + 1 ; --i) {
                newv[i] = newv[i - 1];
            }
            newv[idxA + 1] = vb;
        } else {
            for(int i = idxB; i <= idxA - 1 ; ++i) {
                newv[i] = newv[i + 1];
            }
            newv[idxA] = vb;
        }
    }
    return newv;
}

bool able_to_dance(int a, int b) {
    if (a==b || !isprime[abs(a)+abs(b)]) return false;
    return (a > 0 && b < 0) || (a < 0 && b > 0);
}

int bfs(vector<int> init) {
    visited.clear();
    queue< vector<int> > arrQ;
    queue<int> countQ;

    arrQ.push(init);
    countQ.push(0);
    visited[getOrd(init)] = true;

    while(!arrQ.empty()) {
        vector<int> arr = arrQ.front(); arrQ.pop();
        int count = countQ.front(); countQ.pop();
        int hashedV = getOrd(arr);

        if(hashedV == 12345678)
            return count;

        for(int i = 0; i < len; ++i)
            for(int j = 0; j < len; ++j)
                if(able_to_dance(arr[i], arr[j]))
                    for (int k = 0; k < 2; ++k) {
                        vector<int> newv = dance(arr, i, j, k);
                        if(visited.find(getOrd(newv)) == visited.end())  {
                            visited[getOrd(newv)] = true;
                            arrQ.push(newv);
                            countQ.push(count + 1);
                        }
                    }
    }

    return -1;
}


int main() {
    int n = 0, counter = 1;
    slave_prime();

    while(scanf("%d", &n) != EOF && n != 0) {
        inp.clear();
        inp.push_back(n);
        for(int i = 0; i < len - 1; ++i) {
            scanf("%d", &n);
            inp.push_back(n);
        }

        printf("Case %d: %d\n", counter++, bfs(inp));
    }
    return 0;
}