kuangbin 专题一 简单搜索

Posted on Edited on In

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

POJ-1321 棋盘问题

在棋盘规定的位置摆放棋子，要求棋子不能同行/列，求方案数。简单记录状态，遍历搜索即可。

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
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 9;
int n, k, ans;
char ch;
bool st[N][N], row[N], col[N];
void dfs(int r, int cnt)
{
    if (r == n)
        return;
    for (int c = 0; c < n; ++c)
        if (st[r][c] && row[r] && col[c])
        {
            st[r][c] = row[r] = col[c] = 0;
            if (cnt + 1 == k)
                ++ans;
            dfs(r + 1, cnt + 1);
            st[r][c] = row[r] = col[c] = 1;
        }
    dfs(r + 1, cnt);
}
int main()
{
    while (scanf("%d%d", &n, &k), ~n)
    {
        memset(st, 0, sizeof st);
        memset(row, 1, sizeof row);
        memset(col, 1, sizeof col);
        ans = 0;
        getchar();
        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                scanf("%c", &ch);
                if (ch == '#')
                    st[i][j] = 1;
            }
            getchar();
        }
        dfs(0, 0);
        printf("%d\n", ans);
    }
    return 0;
}

POJ-2251 Dungeon Master

3D 版囚笼逃脱，BFS搜索最短路即可。

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
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 31;
int L, R, C, ds[] = {0, 0, 1, 0, 0, -1, 0, 0}, ans;
char g[N][N][N];
bool st[N][N][N];
int q[N * N * N][3], hh, tt, w;
int bfs(int i, int j, int k)
{
    hh = tt = 0;
    q[tt][0] = i, q[tt][1] = j, q[tt][2] = k, ++tt;
    memset(st, 0, sizeof st);
    st[i][j][k] = 1;
    w = 0;
    while (tt - hh)
    {
        ++w;
        int sz = tt - hh;
        while (sz--)
        {
            int l = q[hh][0], r = q[hh][1], c = q[hh][2];
            ++hh;
            for (int i = 0; i < 6; ++i)
            {
                int nl = l + ds[i], nr = r + ds[i + 1], nc = c + ds[i + 2];
                if (nl < 0 || nl >= L || nr < 0 || nr >= R || nc < 0 || nc >= C || g[nl][nr][nc] == '#' || st[nl][nr][nc])
                    continue;
                if (g[nl][nr][nc] == 'E')
                    return w;
                st[nl][nr][nc] = 1;
                q[tt][0] = nl, q[tt][1] = nr, q[tt][2] = nc, ++tt;
            }
        }
    }
    return 0;
}
int main()
{
    while (scanf("%d%d%d", &L, &R, &C), L)
    {
        for (int i = 0; i < L; ++i)
        {
            for (int j = 0; j < R; ++j)
                scanf("%s", g[i][j]);
            getchar();
        }
        for (int i = 0; i < L; ++i)
            for (int j = 0; j < R; ++j)
                for (int k = 0; k < C; ++k)
                    if (g[i][j][k] == 'S')
                        ans = bfs(i, j, k);
        if (ans)
            printf("Escaped in %d minute(s).\n", ans);
        else
            puts("Trapped!");
    }
    return 0;
}

POJ-3278 Catch That Cow

1D（数轴） 版最短路。

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
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5 + 1;
int n, k, q[N], hh, tt, w;
bool st[N];
int main()
{
    scanf("%d%d", &n, &k);
    if (n >= k)
    {
        printf("%d\n", n - k);
        return 0;
    }
    q[tt++] = n;
    memset(st, 1, sizeof st);
    while (tt - hh)
    {
        int sz = tt - hh;
        while (sz--)
        {
            int p = q[hh++];
            if (p + 1 == k || p - 1 == k || p * 2 == k)
            {
                printf("%d\n", w + 1);
                return 0;
            }
            if (p + 1 < N && st[p + 1])
                q[tt++] = p + 1, st[p + 1] = 0;
            if (p - 1 >= 0 && st[p - 1])
                q[tt++] = p - 1, st[p - 1] = 0;
            if (p * 2 < N && st[p * 2])
                q[tt++] = p * 2, st[p * 2] = 0;
        }
        ++w;
    }
    return 0;
}

POJ-3279 Fliptile

如果直接枚举每头牛的状态，状态总量将高达 。实际上只需要枚举第一行的状态，就可以按行依次递推剩下的状态，最后检查状态合法性并记录最佳方案即可。

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
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = 15, INF = 0x3f3f3f3f;
int M, N, g[MAXN][MAXN];
int ds[] = {0, 0, -1, 0, 1}, cnt, min_turn = INF;
bool turn[MAXN][MAXN], ans[MAXN][MAXN];
int get_color(int x, int y)
{
    int color = g[x][y];
    for (int i = 0; i < 4; ++i) // left, right, up, center, no need to check downwards.
    {
        int nx = x + ds[i], ny = y + ds[i + 1];
        if (nx >= 0 && nx < M && ny >= 0 && ny < N)
            color ^= turn[nx][ny];
    }
    return color;
}
void dfs()
{
    for (int i = 1; i < M; ++i)     // start from the 2nd line.
        for (int j = 0; j < N; ++j) // for each column.
        {
            if (get_color(i - 1, j)) // if preline is of color 1(black), need to turn current line.
                turn[i][j] = 1, ++cnt;
            if (cnt > min_turn) // pruning.
                return;
        }
    // state of the last line is now calculated.
    // check if it is all white.
    for (int i = 0; i < N; ++i)
        if (get_color(M - 1, i))
            return;
    if (cnt < min_turn)
        memcpy(ans, turn, sizeof turn), min_turn = cnt; // keep the ans.
}
int main()
{
    scanf("%d%d", &M, &N);
    for (int i = 0; i < M; ++i)
        for (int j = 0; j < N; ++j)
            scanf("%d", &g[i][j]);
    for (int i = 0; i < 1 << N; ++i) // enumerate each state of the 1st line.
    {
        cnt = 0;                      // cnt of color turned.
        memset(turn, 0, sizeof turn); // state of current line.
        for (int j = 0; j < N; ++j)
        {

            // start from "000***" to get the one with the least lexicographical ordering.
            turn[0][N - 1 - j] = i >> j & 1;
            if (turn[0][N - 1 - j])
                ++cnt;
        }
        dfs(); // since the 1st line is determined, then the rest are all determined as well.
    }
    if (min_turn == INF)
        puts("IMPOSSIBLE");
    else
        for (int i = 0; i < M; ++i)
        {
            for (int j = 0; j < N; ++j)
            {
                if (j > 0)
                    printf(" ");
                printf("%d", ans[i][j]);
            }
            puts("");
        }
    return 0;
}

POJ-1426 Find The Multiple

给定 ，找只含 0 和 1 的 n 的倍数，将余数作为状态进行搜索即可。

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
#include <cstdio>
#include <string>
using namespace std;
int n, found;
string dividend;
void dfs(int remainder)
{
    if (found)
        return;
    if (remainder == 0)
    {
        found = 1;
        printf("%s\n", dividend.c_str());
        return;
    }
    if (dividend.size() < 100)
    {
        dividend += '0';
        dfs((remainder * 10) % n);
        dividend.erase(dividend.end() - 1);
        dividend += '1';
        dfs((remainder * 10 + 1) % n);
        dividend.erase(dividend.end() - 1);
    }
}
int main()
{
    while (scanf("%d", &n), n)
    {
        dividend = "1";
        found = 0;
        dfs(1 % n);
    }
    return 0;
}

POJ-3126 Prime Path

将一个四位的质数转为另一个四位的质数，每次转一位数，且过程中出现的转换后的数也必须是质数，求转换代价。本题只需使用线性筛列出所有四位数的质数作为搜索空间，再使用 BFS 求最短路即可。

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
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
using namespace std;
const int N = 1e4;
int t, src, dest, st[N], q[N], hh, tt, w;
set<int> primes;
void init()
{
    for (int i = 2; i < N; ++i)
    {
        if (!st[i])
            primes.insert(i);
        for (set<int>::iterator it = primes.begin(); it != primes.end(); ++it)
        {
            if (*it > N / i)
                break;
            st[*it * i] = 1;
            if (i % *it == 0)
                break;
        }
    }
}
int get_nth_digit(int num, int i)
{
    while (i--)
        num /= 10;
    return num % 10;
}
int replace_nth_digit(int num, int i, int digit)
{
    int p = pow(10, i);
    int nth_digit = get_nth_digit(num, i);
    return num - nth_digit * p + digit * p;
}
int bfs()
{
    memset(st, 0, sizeof st);
    if (src == dest)
        return 0;
    w = hh = tt = 0;
    q[tt++] = src;
    st[src] = 1;
    while (tt - hh)
    {
        int sz = tt - hh;
        while (sz--)
        {
            int prime = q[hh++];
            if (prime == dest)
                return w;
            for (int i = 3; i >= 0; --i)
            {
                for (int j = 0; j <= 9; ++j)
                {
                    if (i == 3 && j == 0 || j == get_nth_digit(prime, i))
                        continue;
                    int next_num = replace_nth_digit(prime, i, j);
                    if (st[next_num])
                        continue;
                    if (primes.count(next_num))
                        st[next_num] = 1, q[tt++] = next_num;
                }
            }
        }
        ++w;
    }
    return -1;
}
int main()
{
    scanf("%d", &t);
    init();
    while (t--)
    {
        scanf("%d%d", &src, &dest);
        printf("%d\n", bfs());
    }
    return 0;
}

POJ-3087 Shuffle’m Up

按题意转换状态，并记录之，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
#include <iostream>
#include <set>
using namespace std;
int t, ans;
string s1, s2, s3;
string shuffle(string a, string b)
{
    string res;
    for (int i = 0; i < a.size(); ++i)
        res += b[i], res += a[i];
    return res;
}
int main()
{
    cin >> t;
    for (int i = 1, n; i <= t; ++i)
    {
        cin >> n;
        cin >> s1 >> s2 >> s3;
        set<string> memo;
        string t = shuffle(s1, s2);
        ans = 1;
        do
        {
            if (t == s3)
                break;
            if (memo.count(t))
            {
                ans = -1;
                break;
            }
            memo.insert(t);
            t = shuffle(t.substr(0, n), t.substr(n, n));
            ++ans;
        } while (1);
        cout << i << " " << ans << endl;
    }
    return 0;
}

POJ-3414 Pots

多个容器间液体倒来倒去的问题。BFS 搜索并记录最短路即可。

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
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 101;
int a, b, c, w;
bool st[N][N];
string ans;
struct node
{
    string path;
    int x, y;
};
void bfs()
{
    queue<node> q;
    q.push({"", 0, 0});
    memset(st, 1, sizeof st);
    st[0][0] = 0;
    while (q.size())
    {
        int sz = q.size();
        while (sz--)
        {
            node t = q.front();
            q.pop();
            string path = t.path;
            int x = t.x, y = t.y;
            if (x == c || y == c)
            {
                ans = path;
                return;
            }
            // "1" => fill(1)
            if (x < a && st[a][y])
            {
                q.push({path + "1", a, y});
                st[a][y] = 0;
            }
            // "2" => DROP(1)
            if (x > 0 && st[0][y])
            {
                q.push({path + "2", 0, y});
                st[0][y] = 0;
            }
            // "3" => POUR(1,2)
            if (x > 0 && y < b)
            {
                int d = min(b - y, x);
                if (st[x - d][y + d])
                {
                    q.push({path + "3", x - d, y + d});
                    st[x - d][y + d] = 0;
                }
            }
            // "4" => fill(2)
            if (y < b && st[x][b])
            {
                q.push({path + "4", x, b});
                st[x][b] = 0;
            }
            // "5" => DROP(2)
            if (y > 0 && st[x][0])
            {
                q.push({path + "5", x, 0});
                st[x][0] = 0;
            }
            // "6" => POUR(2,1)
            if (y > 0 && x < a)
            {
                int d = min(a - x, y);
                if (st[x + d][y - d])
                {
                    q.push({path + "6", x + d, y - d});
                    st[x + d][y - d] = 0;
                }
            }
        }
        ++w;
    }
}
int main()
{
    cin >> a >> b >> c;
    bfs();
    if (ans.size())
    {
        cout << w << endl;
        for (int i = 0; i < w; ++i)
        {
            char c = ans[i];
            if (c == '1')
                cout << "FILL(1)" << endl;
            else if (c == '2')
                cout << "DROP(1)" << endl;
            else if (c == '3')
                cout << "POUR(1,2)" << endl;
            else if (c == '4')
                cout << "FILL(2)" << endl;
            else if (c == '5')
                cout << "DROP(2)" << endl;
            else if (c == '6')
                cout << "POUR(2,1)" << endl;
        }
    }
    else
    {
        cout << "impossible" << endl;
    }
    return 0;
}

FZU-2150 Fire Game

双源 BFS。

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
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
const int N = 10, INF = 0x3f3f3f3f;
int t, n, m, grass, ans, ds[] = {1, 0, -1, 0, 1};
char c;
bool g[N][N], st[N][N];
struct Node
{
    int x, y;
} nodes[N * N];
int bfs(Node a, Node b)
{
    memset(st, 1, sizeof st);
    queue<Node> q;
    int cnt = 0, w = -1;
    q.push({a.x, a.y}), st[a.x][a.y] = 0;
    if (st[b.x][b.y])
        q.push({b.x, b.y}), st[b.x][b.y] = 0;
    while (q.size())
    {
        int sz = q.size();
        while (sz--)
        {
            Node t = q.front();
            q.pop();
            ++cnt;
            int x = t.x, y = t.y;
            for (int i = 0; i < 4; ++i)
            {
                int nx = x + ds[i], ny = y + ds[i + 1];
                if (~nx && nx < n && ~ny && ny < m && g[nx][ny] && st[nx][ny])
                {
                    st[nx][ny] = 0;
                    q.push({nx, ny});
                }
            }
        }
        if (++w > ans)
            break;
    }
    return cnt == grass ? w : INF;
}
int main()
{
    cin >> t;
    for (int i = 1; i <= t; ++i)
    {
        memset(g, 0, sizeof g);
        grass = 0;
        ans = INF;
        cin >> n >> m;
        for (int j = 0; j < n; ++j)
            for (int k = 0; k < m; ++k)
            {
                cin >> c;
                if (c == '#')
                    g[j][k] = 1, nodes[grass++] = {j, k};
            }
        for (int j = 0; j < grass; ++j)
            for (int k = j; k < grass; ++k)
                ans = min(ans, bfs(nodes[j], nodes[k]));
        cout << "Case " << i << ": " << (ans == INF ? -1 : ans) << endl;
    }
    return 0;
}

UVA-11624 Fire!

多源（火和人） BFS。只要人比火快一步到达地图边缘就算作逃生成功。

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 <queue>
#include <cstring>
using namespace std;
const int N = 1000;
int T, R, C, ds[] = {1, 0, -1, 0, 1};
char c;
bool st[N][N];
struct node
{
    int x, y;
};
int bfs(queue<node> fire, queue<node> path)
{
    int w = 1;
    while (path.size())
    {
        int sz = fire.size();
        while (sz--)
        {
            node t = fire.front();
            fire.pop();
            int x = t.x, y = t.y;
            for (int i = 0; i < 4; ++i)
            {
                int nx = x + ds[i], ny = y + ds[i + 1];
                if (~nx && nx < R && ~ny && ny < C && st[nx][ny])
                {
                    st[nx][ny] = 0;
                    fire.push({nx, ny});
                }
            }
        }
        sz = path.size();
        while (sz--)
        {
            node t = path.front();
            path.pop();
            int x = t.x, y = t.y;
            for (int i = 0; i < 4; ++i)
            {
                int nx = x + ds[i], ny = y + ds[i + 1];
                if (nx == -1 || nx >= R || ny == -1 || ny >= C)
                    return w;
                if (st[nx][ny])
                    st[nx][ny] = 0, path.push({nx, ny});
            }
        }
        ++w;
    }
    return -1;
}
int main()
{
    cin >> T;
    while (T--)
    {
        cin >> R >> C;
        memset(st, 0, sizeof st);
        queue<node> fire;
        queue<node> path;
        for (int i = 0; i < R; ++i)
            for (int j = 0; j < C; ++j)
            {
                cin >> c;
                if (c == 'F')
                    fire.push({i, j});
                else if (c == 'J')
                    path.push({i, j});
                else if (c == '.')
                    st[i][j] = 1;
            }
        int ans = bfs(fire, path);
        if (ans == -1)
            cout << "IMPOSSIBLE" << endl;
        else
            cout << ans << endl;
    }
    return 0;
}

POJ-3984 迷宫问题

二维地图，给定出发点和目的地，以及搜索空间（墙或者路），简单 BFS 求最短路即可。

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 <cstdio>
#include <queue>
using namespace std;
int path[25], ds[] = {1, 0, -1, 0, 1}, ans[25];
bool st[25];
queue<int> q;
int main()
{
    for (int i = 0; i < 25; ++i)
        scanf("%d", &st[i]);
    q.push(0);
    st[0] = 1;
    path[0] = -1;
    while (q.size())
    {
        int pos = q.front();
        q.pop();
        for (int i = 0, x = pos / 5, y = pos % 5; i < 4; ++i)
        {
            int nx = x + ds[i], ny = y + ds[i + 1], np = nx * 5 + ny;
            if (~nx && nx < 5 && ~ny && ny < 5 && !st[np])
            {
                st[np] = 1;
                q.push(np);
                path[np] = pos;
            }
        }
    }
    int pos = 24, len = 0;
    do
    {
        ans[len++] = pos;
        pos = path[pos];
    } while (~pos);
    while (--len >= 0)
    {
        int pos = ans[len];
        printf("(%d, %d)\n", pos / 5, pos % 5);
    }
    return 0;
}

HDU-1241 Oil Deposits

给定石油点地图，求石油块总数。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
#include <cstdio>
using namespace std;
const int N = 101;
int m, n, ans;
char grid[N][N];
void dfs(int i, int j)
{
    grid[i][j] = '*';
    for (int x = -1; x <= 1; ++x)
        for (int y = -1; y <= 1; ++y)
            if (x + i >= 0 && x + i < m && y + j >= 0 && y + j < n && grid[x + i][y + j] == '@')
                dfs(x + i, y + j);
}
int main()
{
    while (true)
    {
        scanf("%d%d", &m, &n);
        if (!m)
            break;
        ans = 0;
        for (int i = 0; i < m; ++i)
            scanf("%s", grid[i]);
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j)
                if (grid[i][j] == '@')
                {
                    dfs(i, j);
                    ++ans;
                }
        printf("%d\n", 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
#include <cstdio>
#include <numeric>
using namespace std;
const int N = 100;
int m, n, ans, p[N * N];
char grid[N][N];
int find(int x)
{
    return x == p[x] ? x : p[x] = find(p[x]);
}
void unite(int i, int j)
{
    for (int x = -1; x <= 1; ++x)
        for (int y = -1; y <= 1; ++y)
            if (x + i >= 0 && x + i < m && y + j >= 0 && y + j < n && grid[x + i][y + j] == '@')
            {
                int p1 = find(i * n + j), p2 = find((x + i) * n + y + j);
                if (p1 != p2)
                    p[p1] = p2;
            }
}
int main()
{
    while (true)
    {
        scanf("%d%d", &m, &n);
        if (!m)
            break;
        ans = 0;
        iota(p, p + m * n, 0);
        for (int i = 0; i < m; ++i)
            scanf("%s", grid[i]);
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j)
                if (grid[i][j] == '@')
                    unite(i, j);
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j)
                if (grid[i][j] == '@' && p[i * n + j] == i * n + j)
                    ++ans;
        printf("%d\n", ans);
    }
    return 0;
}

HDU-1495 非常可乐

还是多个容器间液体倒来倒去的问题。BFS 所有最短路。

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
#include <cstdio>
#include <cstring>
#include <queue>
#include <tuple>
using namespace std;
const int N = 101;
int w[3];
bool st[N][N];
void bfs()
{
    memset(st, 1, sizeof(st));
    st[0][0] = 0;
    queue<tuple<int, int, int>> q;
    q.push({w[0], 0, 0});
    int d = 0;
    while (q.size())
    {
        int sz = q.size();
        while (sz--)
        {
            auto [a, b, c] = q.front();
            q.pop();
            if (a == b && c == 0 || a == c && b == 0 || b == c && a == 0)
            {
                printf("%d\n", d);
                return;
            }
            for (int i = 0; i < 3; ++i)
                for (int j = 0; j < 3; ++j)
                {
                    int d[] = {a, b, c};
                    if (i != j && d[i] > 0 && d[j] < w[j])
                    {
                        int h = min(w[j] - d[j], d[i]);
                        d[j] += h, d[i] -= h;
                        if (st[d[1]][d[2]])
                        {
                            q.push({d[0], d[1], d[2]});
                            st[d[1]][d[2]] = 0;
                        }
                    }
                }
        }
        ++d;
    }
    puts("NO");
}
int main()
{
    while (1)
    {
        scanf("%d%d%d", &w[0], &w[1], &w[2]);
        if (!w[0])
            break;
        if (w[0] & 1) // can NOT be equally divided.
            puts("NO");
        else
            bfs();
    }
    return 0;
}

HDU-2612 Find a way

双源多目的地最短路。分两次搜索，叠加统计各目的地的路程。（注意：因为有禁止通行的道路，所以有些目的地是无法到达的）。

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 <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int N = 201;
int n, m, ds[] = {1, 0, -1, 0, 1}, d[N][N];
char g[N][N];
bool st[N][N];
void bfs(int i, int j)
{
    queue<pair<int, int>> q;
    q.emplace(i, j);
    memset(st, 0, sizeof st);
    st[i][j] = 1;
    int w = 0;
    while (q.size())
    {
        ++w;
        int sz = q.size();
        while (sz--)
        {
            auto [x, y] = q.front();
            q.pop();
            for (int k = 0; k < 4; ++k)
            {
                int nx = x + ds[k], ny = y + ds[k + 1];
                if (nx < 0 || nx >= n || ny < 0 || ny >= m || g[nx][ny] == '#' || st[nx][ny])
                    continue;
                st[nx][ny] = 1;
                if (g[nx][ny] == '@')
                    d[nx][ny] += w;
                q.emplace(nx, ny);
            }
        }
    }
}
int main()
{
    while (~scanf("%d%d", &n, &m))
    {
        int ans = 0x3f3f3f3f;
        memset(d, 0, sizeof d);
        for (int i = 0; i < n; ++i)
            scanf("%s", g[i]);
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j)
                if (g[i][j] == 'Y' || g[i][j] == 'M')
                {
                    bfs(i, j);
                }
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j)
                if (g[i][j] == '@' && d[i][j] != 0)
                    ans = min(ans, d[i][j]);
        printf("%d\n", ans * 11);
    }
    return 0;
}