kuangbin 专题二 搜索进阶

Posted on Edited on In

题目详单见 [kuangbin带你飞]专题1-23。
算法介绍见 搜索部分简介 - OI Wiki。

HDU-1043 Eight

用康托展开将状态映射成排列数的字典序下标，然后

  • 用 BFS 预处理初始状态（123456789）到其他所有状态的路径，
  • 或者结合数学上八数码问题是否有解的判别方法和 A* 算法（有解时）。
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
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int N = 9, M = 362880;
int fact[] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};
int d[] = {-3, -1, 1, 3};
string ds = "drlu"; // reversed order, which is end => start.
string path[M];
bool st[M];
int cantor(int a[])
{
    int res = 0;
    for (int i = 0; i < 9; ++i)
    {
        int cnt = 0;
        for (int j = i + 1; j < 9; ++j)
            if (a[j] < a[i])
                ++cnt;
        res += cnt * fact[9 - i - 1];
    }
    return res;
}
void bfs()
{
    queue<int> q;
    q.push(123456789);
    st[0] = 1;
    while (q.size())
    {
        int num = q.front(), pos_of_nine, a[9];
        q.pop();
        for (int i = 8, x = num; i >= 0; --i)
        {
            a[i] = x % 10;
            if (a[i] == 9)
                pos_of_nine = i;
            x /= 10;
        }
        int idx = cantor(a);
        for (int i = 0; i < 4; ++i) // drlu
        {
            if (pos_of_nine == 0 && (i == 0 || i == 1)    //
                || pos_of_nine == 1 && i == 0             //
                || pos_of_nine == 2 && (i == 0 || i == 2) //
                || pos_of_nine == 3 && i == 1             //
                || pos_of_nine == 5 && i == 2             //
                || pos_of_nine == 6 && (i == 1 || i == 3) //
                || pos_of_nine == 7 && i == 3             //
                || pos_of_nine == 8 && (i == 2 || i == 3))
                continue;
            int next_pos_of_nine = pos_of_nine + d[i];
            swap(a[pos_of_nine], a[next_pos_of_nine]);
            int next_idx = cantor(a);
            if (!st[next_idx])
            {
                st[next_idx] = 1;
                path[next_idx] = path[idx] + ds[i];
                int next_num = 0;
                for (int j = 0; j < 9; ++j)
                    next_num = next_num * 10 + a[j];
                q.push(next_num);
            }
            swap(a[pos_of_nine], a[next_pos_of_nine]);
        }
    }
}
int char_to_int(char ch)
{
    return ch == 'x' ? 9 : ch - '0';
}
int main()
{
    bfs();
    char ch;
    int target[9];
    while (cin >> ch)
    {
        target[0] = char_to_int(ch);
        for (int i = 1; i < 9; ++i)
        {
            cin >> ch;
            target[i] = char_to_int(ch);
        }
        int idx = cantor(target);
        if (!st[idx])
            puts("unsolvable");
        else
        {
            for (int i = path[idx].size() - 1; i >= 0; --i)
                cout << path[idx][i];
            cout << endl;
        }
    }
    return 0;
}
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
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
using pis = pair<int, string>;
const int N = 9, M = 362880;
int fact[] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};
int d[] = {3, 1, -1, -3};
string ds = "drlu";
string target = "123456789";
bool st[M];
int dist[M];
int cantor(string state)
{
    int res = 0;
    for (int i = 0; i < 9; ++i)
    {
        int cnt = 0;
        for (int j = i + 1; j < 9; ++j)
            if (state[j] < state[i])
                ++cnt;
        res += cnt * fact[8 - i];
    }
    return res;
}
int f(string state)
{
    int res = 0;
    for (int i = 0; i < 9; ++i)
        if (state[i] != '9')
            res += abs(i / 3 - (state[i] - '1') / 3) + abs(i % 3 - (state[i] - '1') % 3);
    return res;
}
string bfs(string start)
{
    priority_queue<pis, vector<pis>, greater<pis>> q;
    memset(st, 0, sizeof st);
    memset(dist, 0x3f, sizeof dist);
    string path[M];
    q.emplace(f(start), start);
    dist[cantor(start)] = 0;
    while (q.size())
    {
        auto [_, state] = q.top();
        q.pop();
        if (state == target)
            break;

        int idx = cantor(state), pos_of_nine;
        if (st[idx])
            continue;
        st[idx] = 1;
        for (int i = 0; i < 9; ++i)
            if (state[i] == '9')
            {
                pos_of_nine = i;
                break;
            }
        for (int i = 0; i < 4; ++i) // drlu
        {
            if (pos_of_nine == 0 && (i == 2 || i == 3)    //
                || pos_of_nine == 1 && i == 3             //
                || pos_of_nine == 2 && (i == 1 || i == 3) //
                || pos_of_nine == 3 && i == 2             //
                || pos_of_nine == 5 && i == 1             //
                || pos_of_nine == 6 && (i == 0 || i == 2) //
                || pos_of_nine == 7 && i == 0             //
                || pos_of_nine == 8 && (i == 0 || i == 1))
                continue;
            int next_pos_of_nine = pos_of_nine + d[i];
            swap(state[pos_of_nine], state[next_pos_of_nine]);
            int next_idx = cantor(state);
            if (dist[next_idx] > dist[idx] + 1)
            {
                dist[next_idx] = dist[idx] + 1;
                path[next_idx] = path[idx] + ds[i];
                q.emplace(f(state) + dist[next_idx], state);
            }
            swap(state[pos_of_nine], state[next_pos_of_nine]);
        }
    }
    return path[0];
}
int main()
{
    char ch[9];
    while (cin >> ch[0])
    {
        for (int i = 1; i < 9; ++i)
            cin >> ch[i];
        string start, seq;
        for (int i = 0; i < 9; ++i)
        {
            if (ch[i] == 'x')
                start += '9';
            else
                start += ch[i], seq += ch[i];
        }
        int cnt = 0;
        for (int i = 0; i < 8; ++i)
            for (int j = i + 1; j < 8; ++j)
                if (seq[i] > seq[j])
                    ++cnt;
        if (cnt & 1)
            puts("unsolvable");
        else
            cout << bfs(start) << endl;
    }
    return 0;
}

HDU-3567 Eight II

跟上一题相比，测试用例变多，每个用例指定了起始点和终点，对应的还是可以

  • 预处理九种基本的起始点，再将每个用例的起始点映射成基本起始点中的一个，再按照同样的映射规则将终点作映射，最后跟上一题一样用 BFS 搜索并记录方案。
  • 或者，因为题目确保起始点能到达终点，所以对每个用例都可以直接用 IDA* 算法搜索路径。
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
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 9, M = 362880;
int t, fact[] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};
string ds = "dlru"; // direction (start => end), lexicographically ordered.
int d[] = {3, -1, 1, -3};
int st[N][M], path[N][M];
int cantor(int a[])
{
    int res = 0;
    for (int i = 0; i < N; ++i)
    {
        int cnt = 0;
        for (int j = i + 1; j < N; ++j)
            if (a[j] < a[i])
                ++cnt;
        res += cnt * fact[N - i - 1];
    }
    return res;
}
int array_to_int(int a[])
{
    int res = 0;
    for (int i = 0; i < 9; ++i)
        res = res * 10 + a[i];
    return res;
}
void bfs(int start[], int state_idx)
{
    queue<int> q;
    int num = array_to_int(start), idx = cantor(start), a[9];
    q.push(num), st[state_idx][idx] = 1;
    while (q.size())
    {
        int num = q.front(), pos_of_nine;
        q.pop();
        for (int i = 8, x = num; i >= 0; --i)
        {
            a[i] = x % 10;
            if (a[i] == 9)
                pos_of_nine = i;
            x /= 10;
        }
        int idx = cantor(a);
        for (int i = 0; i < 4; ++i) // dlru
        {
            if (pos_of_nine == 0 && (i == 1 || i == 3)    //
                || pos_of_nine == 1 && i == 3             //
                || pos_of_nine == 2 && (i == 2 || i == 3) //
                || pos_of_nine == 3 && i == 1             //
                || pos_of_nine == 5 && i == 2             //
                || pos_of_nine == 6 && (i == 1 || i == 0) //
                || pos_of_nine == 7 && i == 0             //
                || pos_of_nine == 8 && (i == 0 || i == 2))
                continue;
            int next_pos_of_nine = pos_of_nine + d[i];
            swap(a[pos_of_nine], a[next_pos_of_nine]);
            int next_idx = cantor(a);
            if (st[state_idx][next_idx] == -1)
            {
                st[state_idx][next_idx] = i;
                path[state_idx][next_idx] = idx;
                int next_num = 0;
                for (int j = 0; j < 9; ++j)
                    next_num = next_num * 10 + a[j];
                q.push(next_num);
            }
            swap(a[pos_of_nine], a[next_pos_of_nine]);
        }
    }
}
void init()
{
    int state[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    memset(st, -1, sizeof st);
    memset(path, -1, sizeof path);
    for (int i = 8; i >= 0; --i) // list all possible basic states.
    {
        bfs(state, i); // search all the target states that current statge can go to and record down the path.
        if (i)
            swap(state[i], state[i - 1]);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    init();
    string s;
    int map_to_basic_state[9], to[9], idx_of_basic_state;
    cin >> t;
    for (int _ = 1; _ <= t; ++_)
    {
        cin >> s;
        for (int i = 0, cnt = 1; i < 9; ++i) // map state to one of the basic state.
        {
            if (s[i] == 'X')
                idx_of_basic_state = i;
            else
                map_to_basic_state[s[i] - '0'] = cnt++;
        }
        cin >> s;
        for (int i = 0; i < 9; ++i) // then map target state accordingly.
        {
            if (s[i] == 'X')
                to[i] = 9;
            else
                to[i] = map_to_basic_state[s[i] - '0'];
        }
        int idx_of_target_state = cantor(to);
        string ans;
        while (idx_of_target_state != -1)
        {
            ans += ds[st[idx_of_basic_state][idx_of_target_state]];
            idx_of_target_state = path[idx_of_basic_state][idx_of_target_state];
        }
        cout << "Case " << _ << ": " << (ans.size() - 1) << endl;
        for (int i = ans.size() - 2; i >= 0; --i)
            cout << ans[i];
        cout << endl;
    }
    return 0;
}
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
#include <iostream>
using namespace std;
using pis = pair<int, string>;
int t, depth;
string now, target;
int target_pos[8];
string ds = "dlru"; // direction (start => end), lexicographically ordered.
int dx[] = {1, 0, 0, -1};
int dy[] = {0, -1, 1, 0};
int path[100];
int f()
{
    int res = 0;
    for (int i = 0; i < 9; ++i)
        if (now[i] != 'X')
        {
            int target_num = now[i] - '1';
            res += abs(i / 3 - target_pos[target_num] / 3) + abs(i % 3 - target_pos[target_num] % 3);
        }
    return res;
}
bool dfs(int u)
{
    if (f() + u > depth)
        return 0;
    if (now == target)
        return 1;
    int x_pos;
    for (int i = 0; i < 9; ++i)
        if (now[i] == 'X')
        {
            x_pos = i;
            break;
        }
    int x = x_pos / 3, y = x_pos % 3;
    for (int i = 0; i < 4; ++i)
    {
        int nx = x + dx[i], ny = y + dy[i];
        if (u != 0 && i + path[u - 1] == 3) // path[u] contradicts to path[u-1].
            continue;
        if (nx < 0 || nx >= 3 || ny < 0 || ny >= 3)
            continue;
        swap(now[x * 3 + y], now[nx * 3 + ny]);
        path[u] = i;
        if (dfs(u + 1))
            return 1;
        swap(now[x * 3 + y], now[nx * 3 + ny]);
    }
    return 0;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> t;
    for (int _ = 1; _ <= t; ++_)
    {
        cin >> now >> target;
        for (int i = 0; i < 9; ++i)
            if (target[i] != 'X')
                target_pos[target[i] - '1'] = i;
        for (depth = 0;; ++depth)
            if (dfs(0))
                break;
        cout << "Case " << _ << ": " << depth << endl;
        for (int i = 0; i < depth; ++i)
            cout << ds[path[i]];
        cout << endl;
    }
    return 0;
}

HDU-2181 哈密顿绕行世界问题

按字典序将路径排序再 DFS 即可。

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
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int g[21][3], m, path[21], ans_cnt;
bool st[21];
void dfs(int u, int path_idx)
{
    st[u] = 1;
    path[path_idx] = u;
    for (int i = 0; i < 3; ++i)
    {
        int v = g[u][i];
        if (!st[v])
            dfs(v, path_idx + 1);
        else if (v == m && path_idx == 20)
        {
            cout << ++ans_cnt << ": ";
            for (int j = 1; j <= 20; ++j)
                cout << " " << path[j];
            cout << " " << m << endl;
        }
    }
    st[u] = 0;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    for (int i = 1; i <= 20; ++i)
    {
        cin >> g[i][0] >> g[i][1] >> g[i][2];
        sort(g[i], g[i] + 3);
    }
    while (cin >> m, m)
    {
        ans_cnt = 0;
        memset(st, 0, sizeof st);
        dfs(m, 1);
    }
    return 0;
}

HDU-3533 Escape

预处理各个位置在某一时刻是否有子弹，再使用 BFS 或者 A* (注：因为不一定有解，所以 A* 时间复杂度可能很高) 算法寻找逃跑路径。

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
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 101;
int m, n, k, d, ts[N], vs[N], xs[N], ys[N], ds[N];
int dir[5][2] = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}, {0, 0}}; // N, S, E, W, N/A.
bool castle[N][N], bullet[N][N][1001], st[N][N][1001];
queue<pair<int, int>> q;
void init()
{
    memset(bullet, 0, sizeof bullet);
    for (int i = 0; i < k; ++i) // each castle.
    {
        for (int j = 0; j <= d; j += ts[i]) // a bullet shot at each period.
        {
            for (int k = 1;; ++k) // each unit.
            {
                int x = xs[i] + dir[ds[i]][0] * k; // pos of bullet.
                int y = ys[i] + dir[ds[i]][1] * k;
                if (x < 0 || x > m || y < 0 || y > n || castle[x][y])
                    break;          // out of graph, or blcoked by a castle.
                if (k % vs[i] == 0) // position with integer coordinate.
                    if ((j + k / vs[i]) <= d)
                        bullet[x][y][j + k / vs[i]] = 1;
            }
        }
    }
}
void bfs()
{
    memset(st, 0, sizeof st);
    while (q.size())
        q.pop();
    q.emplace(0, 0);
    st[0][0][0] = 1;
    int t = 0;
    while (q.size())
    {
        int sz = q.size();
        while (sz--)
        {
            auto [x, y] = q.front();
            q.pop();
            if (x == m && y == n)
            {
                cout << t << endl;
                return;
            }
            if (t < d)
                for (int i = 0; i < 5; ++i)
                {
                    int nx = x + dir[i][0], ny = y + dir[i][1];
                    if (nx < 0 || nx > m || ny < 0 || ny > n || st[nx][ny][t + 1] //
                        || castle[nx][ny] || bullet[nx][ny][t + 1])
                        continue;
                    st[nx][ny][t + 1] = 1;
                    q.emplace(nx, ny);
                }
        }
        if (++t > d)
            break;
    }
    cout << "Bad luck!" << endl;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    // m and n are the size of the battle ground,
    // k is the number of castles
    // and d is the units of energy Little A initially has.
    while (cin >> m >> n >> k >> d)
    {
        memset(castle, 0, sizeof castle);
        char c;
        for (int i = 0; i < k; ++i)
        {
            // direction, period, velocity, location(x), location(y).
            cin >> c >> ts[i] >> vs[i] >> xs[i] >> ys[i];
            if (c == 'N')
                ds[i] = 0;
            else if (c == 'S')
                ds[i] = 1;
            else if (c == 'E')
                ds[i] = 2;
            else
                ds[i] = 3;
            castle[xs[i]][ys[i]] = 1;
        }
        init();
        bfs();
    }
    return 0;
}
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
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 101;
int m, n, k, d, ts[N], vs[N], xs[N], ys[N], ds[N];
int dir[5][2] = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}, {0, 0}}; // N, S, E, W, N/A.
bool castle[N][N], bullet[N][N][1001], st[N][N][1001];
struct node
{
    int x, y, g, f;
    node(int x, int y, int g, int f) : x(x), y(y), g(g), f(f){};
    bool operator<(const node &a) const
    {
        return f > a.f;
    }
};
priority_queue<node> q;
void init()
{
    memset(bullet, 0, sizeof bullet);
    for (int i = 0; i < k; ++i) // each castle.
    {
        for (int j = 0; j <= d; j += ts[i]) // a bullet shot at each period.
        {
            for (int k = 1;; ++k) // each unit.
            {
                int x = xs[i] + dir[ds[i]][0] * k; // pos of bullet.
                int y = ys[i] + dir[ds[i]][1] * k;
                if (x < 0 || x > m || y < 0 || y > n || castle[x][y])
                    break;          // out of graph, or blcoked by a castle.
                if (k % vs[i] == 0) // position with integer coordinate.
                    if ((j + k / vs[i]) <= d)
                        bullet[x][y][j + k / vs[i]] = 1;
            }
        }
    }
}
int h(int x, int y)
{
    return abs(x - n) + abs(y - m);
}
void bfs()
{
    memset(st, 0, sizeof st);
    while (q.size())
        q.pop();
    q.emplace(0, 0, 0, 0);
    st[0][0][0] = 1;
    while (q.size())
    {
        auto [x, y, g, f] = q.top();
        q.pop();
        if (x == m && y == n)
        {
            cout << g << endl;
            return;
        }
        if (g < d)
            for (int i = 0; i < 5; ++i)
            {
                int nx = x + dir[i][0], ny = y + dir[i][1];
                if (nx < 0 || nx > m || ny < 0 || ny > n || st[nx][ny][g + 1] //
                    || castle[nx][ny] || bullet[nx][ny][g + 1])
                    continue;
                st[nx][ny][g + 1] = 1;
                q.emplace(nx, ny, g + 1, g + h(nx, ny));
            }
    }
    cout << "Bad luck!" << endl;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    // m and n are the size of the battle ground,
    // k is the number of castles
    // and d is the units of energy Little A initially has.
    while (cin >> m >> n >> k >> d)
    {
        memset(castle, 0, sizeof castle);
        char c;
        for (int i = 0; i < k; ++i)
        {
            // direction, period, velocity, location(x), location(y).
            cin >> c >> ts[i] >> vs[i] >> xs[i] >> ys[i];
            if (c == 'N')
                ds[i] = 0;
            else if (c == 'S')
                ds[i] = 1;
            else if (c == 'E')
                ds[i] = 2;
            else
                ds[i] = 3;
            castle[xs[i]][ys[i]] = 1;
        }
        init();
        bfs();
    }
    return 0;
}

HDU-1560 DNA sequence

这题如果单纯用 DFS ，搜索空间比较大，会 TLE。可以用 IDA* 优化搜索过程，先将最长序列的长度作为初始搜索深度，再配合启发函数加速搜索。启发函数可以是，

  • 序列中未匹配部分的最长长度，
  • 或者叠加序列中未匹配的 ACGT 长度（即，至少仍需多少个 A + 至少仍需多少个 C + …）。
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
#include <iostream>
#include <cstring>
#define N 8
using namespace std;
int t, n, ans;
string seq[N];
char dna[] = {'A', 'C', 'G', 'T'};
int now[N];
int target[N];
int bck[40][N];
void dfs(int u, int c)
{
    if (u > ans)
        return;
    if (c == n)
    {
        ans = u;
        return;
    }
    for (int i = 0; i < 4; ++i)
    {
        int cnt = 0;
        bool flag = 0;
        memcpy(bck[u], now, sizeof now);
        for (int j = 0; j < n; ++j)
        {
            if (now[j] < target[j] && seq[j][now[j]] == dna[i])
            {
                if (++now[j] == target[j])
                    ++cnt;
                flag = 1;
            }
        }
        if (flag)
        {
            dfs(u + 1, c + cnt);
            memcpy(now, bck[u], sizeof now);
        }
    }
}
int main()
{
    cin >> t;
    while (t--)
    {
        cin >> n;
        ans = n * 5;
        memset(now, 0, sizeof now);
        for (int i = 0; i < n; ++i)
        {
            cin >> seq[i];
            target[i] = seq[i].size();
        }
        dfs(0, 0);
        cout << ans << endl;
    }
    return 0;
}
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
#include <iostream>
#include <cstring>
#define N 8
using namespace std;
int t, n;
string seq[N];
char dna[] = {'A', 'C', 'G', 'T'};
int now[N], depth;
int target[N];
int bck[40][N];
int f()
{
    int res = 0;
    for (int i = 0; i < n; ++i)
        res = max(res, target[i] - now[i]);
    return res;
}
bool dfs(int u, int c)
{
    if (u + f() > depth)
        return 0;
    if (c == n)
        return 1;
    for (int i = 0; i < 4; ++i)
    {
        bool flag = 0;
        int cnt = 0;
        memcpy(bck[u], now, sizeof now);
        for (int j = 0; j < n; ++j)
        {
            if (now[j] < target[j] && seq[j][now[j]] == dna[i])
            {
                if (++now[j] == target[j])
                    ++cnt;
                flag = 1;
            }
        }
        if (flag)
        {
            if (dfs(u + 1, c + cnt))
                return 1;
            memcpy(now, bck[u], sizeof now);
        }
    }
    return 0;
}
int main()
{
    cin >> t;
    while (t--)
    {
        cin >> n;
        memset(now, 0, sizeof now);
        depth = 0;
        for (int i = 0; i < n; ++i)
        {
            cin >> seq[i];
            target[i] = seq[i].size();
            depth = max(depth, target[i]);
        }
        while (!dfs(0, 0))
            ++depth;
        cout << depth << endl;
    }
    return 0;
}
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
#include <iostream>
#include <cstring>
#define N 8
using namespace std;
int t, n, seq[N][5], cnt[N][4];
int now[N], target[N], depth;
int f()
{
    int res = 0;
    for (int i = 0; i < 4; ++i)
    {
        int max_lack = 0;
        for (int j = 0; j < n; ++j)
            max_lack = max(max_lack, cnt[j][i]);
        res += max_lack;
    }
    return res;
}
bool dfs(int u, int c)
{
    if (u + f() > depth)
        return 0;
    if (c == n)
        return 1;
    for (int i = 0; i < 4; ++i)
    {
        bool flag = 0;
        int cc = 0;
        bool act[n] = {};
        for (int j = 0; j < n; ++j)
        {
            if (now[j] < target[j] && seq[j][now[j]] == i)
            {
                --cnt[j][seq[j][now[j]]], act[j] = 1, flag = 1;
                if (++now[j] == target[j])
                    ++cc;
            }
        }
        if (flag)
        {
            if (dfs(u + 1, c + cc))
                return 1;
            for (int j = 0; j < n; ++j)
                if (act[j])
                    now[j]--, cnt[j][seq[j][now[j]]]++;
        }
    }
    return 0;
}
int main()
{
    cin >> t;
    while (t--)
    {
        cin >> n;
        memset(now, 0, sizeof now);
        memset(cnt, 0, sizeof cnt);
        depth = 0;
        string s;
        for (int i = 0; i < n; ++i)
        {
            cin >> s;
            target[i] = s.size();
            depth = max(depth, target[i]);
            for (int j = 0; j < target[i]; ++j)
                if (s[j] == 'A')
                    seq[i][j] = 0, cnt[i][0]++;
                else if (s[j] == 'C')
                    seq[i][j] = 1, cnt[i][1]++;
                else if (s[j] == 'G')
                    seq[i][j] = 2, cnt[i][2]++;
                else
                    seq[i][j] = 3, cnt[i][3]++;
        }
        while (!dfs(0, 0))
            ++depth;
        cout << depth << endl;
    }
    return 0;
}

ZOJ-2477 Magic Cube

题目限定五步内还原三阶魔方，可以使用 IDA* 搜索。因为每个面的中心颜色是不变的，即目标状态是确定的，又因为每次旋转最多更改同一面三个位置的颜色，所以可以找出与中心颜色差最多的一面，取(最大差值+2)/3
为估价函数。

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 <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
/*
         0  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
*/
// indexes of each points (without centre) in each face.
int idx[6][8] = {
    {0, 1, 2, 3, 5, 6, 7, 8},         //
    {9, 10, 11, 21, 23, 33, 34, 35},  //
    {12, 13, 14, 24, 26, 36, 37, 38}, //
    {15, 16, 17, 27, 29, 39, 40, 41}, //
    {18, 19, 20, 30, 32, 42, 43, 44}, //
    {45, 46, 47, 48, 50, 51, 52, 53}};
int centre[6] = {4, 22, 25, 28, 31, 49}; // centre indexes.
// there are 12 = (clock-wise + counter clock-wisk) * (6 faces)
// kinds of rotation. For each rotation, centre remains, the other
// 20 = (8 cubes) + (3 cubes) * (4 faces) cubes get rotated.
int rotation[12][20] = {
    // face 0.
    // 11 <=> 9, 23 <=> 10, ... , 44 <=> 45.
    {11, 23, 35, 34, 33, 21, 9, 10, 51, 48, 45, 36, 24, 12, 6, 3, 0, 20, 32, 44}, // direction 1.
    {9, 10, 11, 23, 35, 34, 33, 21, 36, 24, 12, 6, 3, 0, 20, 32, 44, 51, 48, 45}, // direction -1.
    // face 1.
    // 14 <=> 12, 13 <=> 24, ... , 35 <=> 47.
    {14, 13, 26, 38, 37, 36, 24, 12, 45, 46, 47, 39, 27, 15, 8, 7, 6, 11, 23, 35}, // direction 1.
    {12, 24, 13, 14, 26, 38, 37, 36, 39, 27, 15, 8, 7, 6, 11, 23, 35, 45, 46, 47}, // direction -1.
    // ...
    {17, 29, 41, 40, 39, 27, 15, 16, 47, 50, 53, 42, 30, 18, 2, 5, 8, 14, 26, 38}, // ...
    {15, 16, 17, 29, 41, 40, 39, 27, 42, 30, 18, 2, 5, 8, 14, 26, 38, 47, 50, 53},
    {18, 19, 20, 32, 44, 43, 42, 30, 53, 52, 51, 33, 21, 9, 0, 1, 2, 17, 29, 41},
    {42, 30, 18, 19, 20, 32, 44, 43, 33, 21, 9, 0, 1, 2, 17, 29, 41, 53, 52, 51},
    {0, 1, 2, 5, 8, 7, 6, 3, 12, 13, 14, 15, 16, 17, 18, 19, 20, 9, 10, 11},
    {6, 3, 0, 1, 2, 5, 8, 7, 15, 16, 17, 18, 19, 20, 9, 10, 11, 12, 13, 14},
    {45, 46, 47, 50, 53, 52, 51, 48, 44, 43, 42, 41, 40, 39, 38, 37, 36, 35, 34, 33},
    {51, 48, 45, 46, 47, 50, 53, 52, 41, 40, 39, 38, 37, 36, 35, 34, 33, 44, 43, 42}};
int t, depth, ans[6];
char ch, a[54];
char get_in()
{
    char ch;
    while (1)
    {
        ch = getchar();
        if (ch >= 'a' && ch <= 'z')
            return ch;
    }
}
char f(char *maze)
{
    int max_diff = 0;
    for (int i = 0; i < 6; ++i)
    {
        int diff = 0;
        for (int j = 0; j < 8; ++j)
            if (maze[idx[i][j]] != maze[centre[i]])
                ++diff;
        max_diff = max(max_diff, diff);
    }
    // by 1 rotation,
    // we can swith color of 3 (at most) cubes that are in the same face.
    return (max_diff + 2) / 3;
}
bool dfs(int u, char *a, int pre)
{
    if (u + f(a) > depth)
        return 0;
    if (u == depth)
        return 1;
    for (int i = 0; i < 12; ++i)
    {
        if ((i ^ pre) == 1) // rotate back?
            continue;       // no!
        char b[54];
        memcpy(b, a, 54 * sizeof(char));
        ans[depth - u] = i;
        for (int j = 0; j < 20; ++j)
            b[rotation[i][j]] = a[rotation[i ^ 1][j]];
        if (dfs(u + 1, b, i))
            return 1;
    }
    return 0;
}
int main()
{
    scanf("%d", &t);
    while (t--)
    {
        for (int i = 0; i < 54; ++i)
            a[i] = get_in();
        depth = f(a);
        if (depth == 0)
        {
            printf("0\n");
            continue;
        }
        for (; depth <= 5; ++depth)
            if (dfs(0, a, -1))
            {
                printf("%d\n", depth);
                for (int j = depth; j > 0; --j)
                    printf("%d %d%c", ans[j] / 2, (ans[j] & 1) ? -1 : 1, j > 1 ? ' ' : '\n');
                break;
            }
        if (depth > 5)
            printf("-1\n");
    }
    return 0;
}

HDU-3085 Nightmare Ⅱ

双向 BFS，M/G 走，用与 Z 的距离判定是否会被抓到，只要双方都能走到一个不被抓到的点即成功。

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
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int N = 800;
int t, n, m, z, zs[2][2], step, ds[] = {1, 0, -1, 0, 1};
char g[N][N];
queue<pair<int, int>> q[2];
bool st[2][N][N];
bool catched(int x, int y, int step)
{
    return abs(x - zs[0][0]) + abs(y - zs[0][1]) <= 2 * step || //
           abs(x - zs[1][0]) + abs(y - zs[1][1]) <= 2 * step;
}
bool bfs(int p)
{
    int sz = q[p].size();
    while (sz--)
    {
        auto [x, y] = q[p].front();
        q[p].pop();
        if (catched(x, y, step))
            continue;
        for (int i = 0; i < 4; ++i)
        {
            int nx = x + ds[i], ny = y + ds[i + 1];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m || //
                g[nx][ny] == 'X' || st[p][nx][ny] || catched(nx, ny, step))
                continue;
            st[p][nx][ny] = 1;
            if (st[0][nx][ny] && st[1][nx][ny])
                return 1;
            q[p].emplace(nx, ny);
        }
    }
    return 0;
}
int solve()
{
    step = 0;
    while (q[0].size() || q[1].size())
    {
        ++step;
        if (bfs(0))
            return step;
        if (bfs(0))
            return step;
        if (bfs(0))
            return step;
        if (bfs(1))
            return step;
    }
    return -1;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> t;
    while (t--)
    {
        z = 0;
        memset(st, 0, sizeof st);
        while (q[0].size())
            q[0].pop();
        while (q[1].size())
            q[1].pop();
        cin >> n >> m;
        for (int i = 0; i < n; ++i)
        {
            cin >> g[i];
            for (int j = 0; j < m; ++j)
            {
                if (g[i][j] == 'Z')
                {
                    zs[z][0] = i, zs[z][1] = j;
                    z++;
                }
                else if (g[i][j] == 'M')
                    q[0].emplace(i, j), st[0][i][j] = 1;
                else if (g[i][j] == 'G')
                    q[1].emplace(i, j), st[1][i][j] = 1;
            }
        }
        cout << solve() << endl;
    }
    return 0;
}

HDU-1067 Gap

一眼 BFS，关键是状态表示。可以将数字当作 ASCII 码，转成对应字符，连接成串就是当前状态。

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
#include <cstdio>
#include <cstring>
#include <queue>
#include <string>
#include <unordered_set>
using namespace std;
int t;
string start(32, 1), target(32, 1);
void moveChar(string &str, char ch, int new_idx)
{
    int idx = 0;
    while (idx < 32 && str[idx] != ch)
        ++idx;
    if (idx != 32)
    {
        str[new_idx] = ch;
        str[idx] = 1;
    }
}
int bfs()
{
    queue<string> q;
    q.push(start);
    unordered_set<string> hash;
    hash.insert(start);
    int step = 0;
    while (q.size())
    {
        int sz = q.size();
        while (sz--)
        {
            string u = q.front();
            q.pop();
            if (u == target)
                return step;
            for (int i = 0; i < 4; ++i)
                for (int j = 1; j < 8; ++j)
                {
                    if (u[i * 8 + j] == 1 && u[i * 8 + j - 1] != 1)
                    {
                        string v = u;
                        moveChar(v, u[i * 8 + j - 1] + 1, i * 8 + j);
                        if (hash.find(v) == hash.end())
                        {
                            hash.insert(v);
                            q.push(v);
                        }
                    }
                }
        }
        ++step;
    }
    return -1;
}
int main()
{
    for (int i = 0; i < 4; ++i)
        for (int j = 0; j < 7; ++j)
            target[i * 8 + j] = (i + 1) * 10 + (j + 1);
    scanf("%d", &t);
    start = string(32, 1);
    while (t--)
    {
        for (int i = 0; i < 4; ++i)
            for (int j = 1, x; j < 8; ++j)
            {
                scanf("%d", &x);
                if (x % 10 == 1)
                    start[(x / 10 - 1) * 8] = x, start[i * 8 + j] = 1;
                else
                    start[i * 8 + j] = x;
            }
        printf("%d\n", bfs());
    }
    return 0;
}

HDU-2102 A计划

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
#include <cstdio>
#include <cstring>
#include <queue>
#include <tuple>
using namespace std;
const int N = 10;
int c, n, m, t, pz, px, py, ds[] = {1, 0, -1, 0, 1};
char g[2][N][N];
queue<tuple<int, int, int>> q;
bool st[2][N][N];
bool bfs()
{
    while (q.size())
        q.pop();
    q.emplace(0, 0, 0);
    memset(st, 0, sizeof st);
    st[0][0][0] = 1;
    while (q.size())
    {
        int sz = q.size();
        while (sz--)
        {
            auto [z, x, y] = q.front();
            q.pop();
            if (g[z][x][y] == 'P')
                return 1;
            for (int i = 0; i < 4; ++i)
            {
                int nx = x + ds[i], ny = y + ds[i + 1],
                    nz = g[z][nx][ny] == '#' ? 1 - z : z;
                if (nx < 0 || nx >= n || ny < 0 || ny >= m)
                    continue;
                if (g[z][nx][ny] == '*')
                    continue;
                if (g[z][nx][ny] == '#' && (g[nz][nx][ny] == '*' || g[nz][nx][ny] == '#'))
                    continue;
                if (st[nz][nx][ny])
                    continue;
                st[nz][nx][ny] = 1;
                q.emplace(nz, nx, ny);
            }
        }
        if (--t < 0)
            return 0;
    }
    return 0;
}
int main()
{
    scanf("%d", &c);
    while (c--)
    {
        scanf("%d%d%d", &n, &m, &t);
        for (int i = 0; i < 2; ++i)
            for (int j = 0; j < n; ++j)
                scanf("%s", g[i][j]);
        puts(bfs() ? "YES" : "NO");
    }
    return 0;
}

HDU-3001 Travelling

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
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 11, INF = 0x3f3f3f3f;
int n, m, ans;
int g[N][N];
int st[N];
void dfs(int u, int cnt, int cost)
{
    if (cost >= ans)
        return;
    if (cnt == n)
    {
        ans = cost;
        return;
    }
    ++st[u];
    for (int v = 1; v <= n; ++v)
        if (u != v && g[u][v] != INF && st[v] < 2)
            dfs(v, cnt + (st[v] == 0), cost + g[u][v]);
    --st[u];
}
int main()
{
    while (~scanf("%d%d", &n, &m))
    {
        memset(g, 0x3f, sizeof g);
        ans = INF;
        for (int i = 0, a, b, c; i < m; ++i)
        {
            scanf("%d%d%d", &a, &b, &c);
            g[a][b] = g[b][a] = min(g[a][b], c);
        }
        for (int i = 1; i <= n; ++i)
            dfs(i, 1, 0);
        printf("%d\n", ans == INF ? -1 : ans);
    }
    return 0;
}
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
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int pow3[] = {1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049};
const int N = 11, M = 59049, INF = 0x3f3f3f3f;
int n, m, ans;
int g[N][N];
int f[M][N];
int st[M];
void init()
{
    for (int i = 0; i < M; ++i) // state i.
    {
        int t = i;
        for (int j = 10; j >= 0; --j) // position j.
            if (t / pow3[j])          // flagged or not.
                ++st[i], t %= pow3[j];
    }
}
int main()
{
    init();
    while (~scanf("%d%d", &n, &m))
    {
        memset(g, 0x3f, sizeof g);
        memset(f, 0x3f, sizeof f);
        ans = INF;
        for (int i = 0, a, b, c; i < m; ++i)
        {
            scanf("%d%d%d", &a, &b, &c);
            --a, --b;
            g[a][b] = g[b][a] = min(g[a][b], c);
        }
        for (int i = 0; i < n; ++i)
            f[pow3[i]][i] = 0;
        for (int i = 0; i < pow3[n]; ++i)
            for (int j = 0; j < n; ++j)
            {
                if ((i / pow3[j]) % 3) // if state i flagged in position j.
                    for (int k = 0; k < n; ++k)
                        // k => j.
                        f[i][j] = min(f[i][j], f[i - pow3[j]][k] + g[k][j]);
                if (st[i] == n) // valid final state.
                    ans = min(ans, f[i][j]);
            }
        printf("%d\n", ans == INF ? -1 : ans);
    }
    return 0;
}