1. POJ1321 棋盘问题

题目链接

题意：在给定形状的棋盘上摆无区别棋子，任意两棋子不同行或同列，求摆 k 个棋子所有方案数。

 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 <cstdio>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
typedef long long ll;
const int INF = 2e9;

int n, k, ans, cnt;
char s[10][10], v[10];

void dfs(int row) {
    if (cnt == k) { ans++; return; }
    if (row > n) return;
    for (int i = 0; i < n; ++i)
        if (s[row][i] == '#' && !v[i]) {
            v[i] = 1;
            cnt++;
            dfs(row + 1);
            v[i] = 0;
            cnt--;
        }
    dfs(row + 1);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    while (cin >> n >> k && n != -1) {
        ans = cnt = 0;
        for (int i = 1; i <= n; ++i) {
            cin >> s[i];
        }
        dfs(1);
        printf("%d\n", ans);
    }
    return 0;
}

2. POJ2251 Dungeon Master

题目链接

题意：在$L\times R\times 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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 2e9, N = 35;

struct node {
    int x, y, z, cnt;
    node(int x = 0, int y = 0, int z = 0, int cnt = 0) : x(x), y(y), z(z), cnt(cnt) {}
};

node st, ed;
char mp[N][N][N];
int l, r, c;
int v[N][N][N];
int dx[6] = {0, 0, 0, 0, 1, -1};
int dy[6] = {1, 0, -1, 0, 0, 0};
int dz[6] = {0, 1, 0, -1, 0, 0};

bool valid(int x, int y, int z) {
    if (x >= 1 && x <= l && y >= 1 && y <= r && z >= 0 && z < c && !v[x][y][z] && mp[x][y][z] != '#') return 1;
    return 0;
}

int bfs() {
    memset(v, 0, sizeof(v));
    queue<node> q;
    q.push(st);
    v[st.x][st.y][st.z] = 1;
    while (!q.empty()) {
        node cur = q.front();
        q.pop();
        if (cur.x == ed.x && cur.y == ed.y && cur.z == ed.z) return cur.cnt;
        for (int i = 0; i < 6; ++i) {
            node tmp;
            tmp.x = cur.x + dx[i];
            tmp.y = cur.y + dy[i];
            tmp.z = cur.z + dz[i];
            if (valid(tmp.x, tmp.y, tmp.z)) {
                tmp.cnt = cur.cnt + 1;
                q.push(tmp);
                v[tmp.x][tmp.y][tmp.z] = 1;
            }
        }
    }
    return -1;
}

int main() 
{
    while (~scanf("%d%d%d", &l, &r, &c) && l) {
        for (int i = 1; i <= l; ++i) {
            for (int j = 1; j <= r; ++j) {
                scanf("%s", mp[i][j]);
                for (int k = 0; k < c; ++k) {
                    if (mp[i][j][k] == 'S') {
                        st = node(i, j, k);
                    }
                    else if (mp[i][j][k] == 'E') {
                        ed = node(i, j, k);
                    }
                }
                getchar();
            }
        }
        int ans = bfs();
        if (ans != -1) printf("Escaped in %d minute(s).\n", ans);
        else puts("Trapped!");
    }
    return 0;
}

3. POJ3278 Catch That Cow

题目链接

题意：在线段$[0,10^5]$上，农夫 Jorn 在 N，逃跑的奶牛在 K 不动，农夫每分钟可以向左右一步或位置翻倍，求抓到奶牛最短时间。

 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 <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 2e9, N = 1e5 + 5;

int n, k;
int v[N];
int dx[3] = {1, 1, 2}, dy[3] = {1, -1, 0};

void bfs() {
    memset(v, 0, sizeof(v));
    queue<int> q;
    q.push(n);
    v[n] = 1;
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        if (cur == k) return;
        for (int i = 0; i < 3; ++i) {
            int tmp = cur * dx[i] + dy[i];
            if (tmp >= 0 && tmp <= (int)1e5 && !v[tmp]) {
                q.push(tmp);
                v[tmp] = v[cur] + 1;
            }
        }
    }
}

int main()
{
    scanf("%d%d", &n, &k);
    if (n >= k) printf("%d\n", n - k);
    else {
        bfs();
        printf("%d\n", v[k] - 1);
    }
    return 0;
}

4. POJ3279 Fliptile

题目链接

题意：$M\times N$的格子有黑白两面，农夫 Jorn 的牛对格子进行翻转，每次翻转一格，相邻格子也会被翻转，求全部变为白色的最小翻转次数。

  经典二维翻转问题。直接暴力搜是$O(2^{MN})$。我们知道：翻转n次相当于n%2次，翻转顺序不影响结果。按字典序枚举第一行翻转状态，第一行确定后，只有下一行可改变上一行，最后检查最后一行即可。

 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

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 2e9, N = 20;

int t[N][N];
int ans[N][N], flip[N][N];
int m, n, minn = INF;
int dx[] = {0, 1, -1, 0, 0};
int dy[] = {0, 0, 0, 1, -1};

int chk(int r, int c) {
    int sum = t[r][c];
    for (int i = 0; i < 5; ++i) {
        int x = r + dx[i];
        int y = c + dy[i];
        if (x >= 1 && x <= m && y >= 1 && y <= n) {
            sum += flip[x][y];
        }
    }
    return sum & 1;
}

int solve() {
    int tmp = 0;
    for (int i = 2; i <= m; ++i)
        for (int j = 1; j <= n; ++j)
            if (chk(i - 1, j)) flip[i][j] = 1;
    for (int i = 1; i <= n; ++i)
        if (chk(m, i)) return INF;
    for (int i = 1; i <= m; ++i)
        for (int j = 1; j <= n; ++j)
            tmp += flip[i][j];
    return tmp;
}

int main() 
{
    scanf("%d%d", &m, &n);
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            scanf("%d", &t[i][j]);
        }
    }
    for (int i = 0; i < (1 << n); ++i) {
        memset(flip, 0, sizeof(flip));
        for (int j = 0; j < n; ++j) {
            flip[1][n-j] = (i >> j) & 1;
        }
        int cnt = solve();
        if (cnt < minn) {
            minn = cnt;
            memcpy(ans, flip, sizeof(ans));
        }
    }
    if (minn == INF) puts("IMPOSSIBLE");
    else {
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                printf("%d ", ans[i][j]);
            }
            puts("");
        }
    }
    return 0;
}

5. POJ1426 Find The Multiple

题目链接

题意：给定正整数 n，寻找 n 的一个非零倍数 m，m 的十进制表示每一位只含 0 或 1，假定 n 不大于 200 且 m 不多于 100 位。

  对所求数 num 从 1 开始深搜，只有两个方向 num * 10 和 num * 10 + 1，由于 long long 最大值长度为 19 位，所以数长度大于 19 位时 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

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 2e9;

int n, flag;

void dfs(int step, ll num) {
    if (step > 19 || flag) {
        return;
    }
    if (num % n == 0) {
        flag = 1;
        printf("%lld\n", num);
        return;
    }
    dfs(step + 1, num * 10);
    dfs(step + 1, num * 10 + 1);
}

int main() 
{
    while (scanf("%d", &n) && n) {
        flag = 0;
        dfs(1, 1);
    }
    return 0;
}

6. POJ3126 Prime Path

题目链接

题意：给定两个四位素数 a, b，a 可以改变一位变成 c，但仅当 c为四位素数才能改变，求 a 变为 b 的最小次数。

  先筛出判断素数的表，再进行 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

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <cmath>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int N = 1e5 + 5, INF = 2e9;

int isprime[N], vis[N];
int t, a, b, ans;

struct node {
    int num, step;
    node (int num, int step) : num(num), step(step) {}
};

void init() {
    memset(isprime, 1, sizeof(isprime));
    isprime[0] = isprime[1] = 0;
    for (int i = 2; i < N; ++i) {
        if (isprime[i]) {
            if (i > N / i) continue;
            for (int j = i * i; j < N; j += i) {
                isprime[j] = 0;
            }
        }
    }
}

void bfs() {
    queue<node> q;
    q.push(node(a, 0));
    vis[a] = 1;
    while (!q.empty()) {
        node cur = q.front();
        q.pop();
        if (cur.num == b) {
            ans = cur.step;
            break;
        }
        for (int i = 1; i <= 9; ++i) {
            int tmp = cur.num;
            tmp = tmp % 1000 + i * 1000;
            if (isprime[tmp] && !vis[tmp]) {
                vis[tmp] = 1;
                q.push(node(tmp, cur.step + 1));
            }
        }
        for (int i = 0; i <= 9; ++i) {
            int tmp = cur.num;
            tmp = tmp - tmp % 1000 + tmp % 100 + i * 100;
            if (isprime[tmp] && !vis[tmp]) {
                vis[tmp] = 1;
                q.push(node(tmp, cur.step + 1));
            }
        }
        for (int i = 0; i <= 9; ++i) {
            int tmp = cur.num;
            tmp = tmp - tmp % 100 + tmp % 10 + i * 10;
            if (isprime[tmp] && !vis[tmp]) {
                vis[tmp] = 1;
                q.push(node(tmp, cur.step + 1));
            }
        }
        for (int i = 0; i <= 9; ++i) {
            int tmp = cur.num;
            tmp = tmp - tmp % 10 + i;
            if (isprime[tmp] && !vis[tmp]) {
                vis[tmp] = 1;
                q.push(node(tmp, cur.step + 1));
            }
        }
    }
}

int main() 
{
    scanf("%d", &t);
    init();
    while (t--) {
        memset(vis, 0, sizeof(vis));
        ans = INF;
        scanf("%d%d", &a, &b);
        bfs();
        if (ans == INF) {
            puts("Impossible");
        }
        else printf("%d\n", ans);
    }
    return 0;
}

7. POJ3087 Shuffle’m Up

题目链接

题意：给出两个长度为 C 的字符串 s1 和 s2 和一个长度为 2C 的字符串 s12，一次操作为按先 s2 后 s1 的顺序取字符得到一个长度为 2C 的字符串 s，若 s 与 s12 相同输出操作次数，否则 s 前半部分为 s1 后半部分为 s2 继续操作，若无法成功输出 -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

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <map>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 2e9;

int n, c;
string s1, s2, s12, tmp;

int search() {
    map<string, int> vis;
    int cnt = 1;
    while (tmp != s12 && !vis[tmp]) {
        vis[tmp] = 1;
        cnt++;
        s1 = tmp.substr(0, c);
        s2 = tmp.substr(c, c);
        tmp = "";
        for (int i = 0; i < c; ++i) {
            tmp += s2[i];
            tmp += s1[i];
        }
    }
    if (tmp == s12) return cnt;
    return -1;
}

int main() 
{
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &c);
        cin >> s1 >> s2 >> s12;
        tmp = "";
        for (int i = 0; i < c; ++i) {
            tmp += s2[i];
            tmp += s1[i];
        }
        printf("%d %d\n", i, search());
    }
    return 0;
}

8. POJ3414 Pots

题目链接

题意：给定两个容器，分别能装$A$升和$B$升水，有以下操作：

  1. FILL(i) 用水龙头将容器$i(1\le i\le2)$装满。
  2. DROP(i) 将容器$i$排干。
  3. POUR(i,j) 将容器$i$的水倒入容器$j$，操作后容器$j$满则容器$i$有剩余，或者容器$i$空水全部倒入容器$j$。

找出次数最少的操作序列使得任何一个容器恰有$C$升水$(1\le A,B\le100,\ C\le\max(A,B))$。

  bfs优先队列分6种情况入队记录路径即可。

 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

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 2e9;

struct node {
    int vol1, vol2, step;
    string id, path;
    friend bool operator < (const node &x, const node &y) {
        return x.step > y.step;
    }
}now, nex;

int a, b, c, flag;
int vis[105][105];

string op[6] = {"FILL(1)", "FILL(2)", "DROP(1)", "DROP(2)", "POUR(1,2)", "POUR(2,1)"};

void bfs() {
    priority_queue<node> q;
    now.vol1 = 0, now.vol2 = 0, now.step = 0, now.id = "", now.path = "";
    vis[now.vol1][now.vol2] = 1;
    q.push(now);
    while (!q.empty()) {
        now = q.top();
        q.pop();
        if (now.vol1 == c || now.vol2 == c) {
            flag = 1;
            printf("%d\n", now.step);
            for (int i = 0; i < (int)now.path.length(); ++i) {
                cout << op[now.path[i] - '0'] << '\n';
            }
            break;
        }
        for (int i = 0; i < 6; ++i) {
            nex.id = i + '0';
            if (i == 0) {
                nex.vol1 = a;
                nex.vol2 = now.vol2;
            }
            else if (i == 1) {
                nex.vol2 = b;
                nex.vol1 = now.vol1;
            }
            else if (i == 2) {
                nex.vol1 = 0;
                nex.vol2 = now.vol2;
            }
            else if (i == 3) {
                nex.vol2 = 0;
                nex.vol1 = now.vol1;
            }
            else if (i == 4) {
                if (now.vol1 + now.vol2 > b) {
                    nex.vol1 = now.vol1 + now.vol2 - b;
                    nex.vol2 = b;
                }
                else {
                    nex.vol1 = 0;
                    nex.vol2 = now.vol1 + now.vol2;
                }
            }
            else if (i == 5) {
                if (now.vol1 + now.vol2 > a) {
                    nex.vol1 = a;
                    nex.vol2 = now.vol1 + now.vol2 - a;
                }
                else {
                    nex.vol1 = now.vol1 + now.vol2;
                    nex.vol2 = 0;
                }
            }
            if (!vis[nex.vol1][nex.vol2]) {
                vis[nex.vol1][nex.vol2] = 1;
                nex.step = now.step + 1;
                nex.path = now.path + nex.id;
                q.push(nex);
            }
        }

    }
    if (!flag) puts("impossible");
}

int main()
{
    scanf("%d%d%d", &a, &b, &c);
    bfs();
    return 0;
}

9. FZU2150 Fire Game

题目链接

题意：在一个$n\times m(1\le n,m\le10)$的板上，板上每一个格子包含草或为空，选任意两个格子放火，火每 1 秒向周围四个格子蔓延，求烧完所有草的最小时间，如果不能输出 -1。

  数据较小，枚举两个点进行 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 <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 2e9, N = 15;

struct point {
    int x, y, step;
    point(int x = 0, int y = 0, int step = 0) : x(x), y(y), step(step) {}
}p[105];

int t, n, m, cnt, ans;
char mp[N][N];
int vis[N][N];
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};

bool chk() {
    for (int i = 1; i <= cnt; ++i)
        if (!vis[p[i].x][p[i].y]) return false;
    return true;
}

int bfs(point a, point b) {
    int res = 0;
    memset(vis, 0, sizeof(vis));
    queue<point> q;
    q.push(a);
    q.push(b);
    vis[a.x][a.y] = 1;
    vis[b.x][b.y] = 1;
    while (!q.empty()) {
        point cur = q.front();
        q.pop();
        for (int i = 0; i < 4; ++i) {
            point tmp = point(cur.x + dx[i], cur.y + dy[i], cur.step + 1);
            if (tmp.x >= 0 && tmp.x < n && tmp.y >= 0 && tmp.y < m && mp[tmp.x][tmp.y] == '#' && !vis[tmp.x][tmp.y]) {
                vis[tmp.x][tmp.y] = 1;
                res = max(res, tmp.step);
                q.push(tmp);
            }
        }
    }
    if (chk()) return res;
    return INF;
}

int main() 
{
    scanf("%d", &t);
    for (int i = 1; i <= t; ++i) {
        scanf("%d%d", &n, &m);
        cnt = 0;
        for (int j = 0; j < n; ++j) {
            scanf("%s", mp[j]);
            for (int k = 0; k < m; ++k) {
                if (mp[j][k] == '#') {
                    p[++cnt] = point(j, k, 0);
                }
            }
        }
        ans = INF;
        for (int j = 1; j <= cnt; ++j) {
            for (int k = j; k <= cnt; ++k) {
                ans = min(bfs(p[j], p[k]), ans);
            }
        }
        printf("Case %d: ", i);
        if (ans == INF) printf("-1\n");
        else printf("%d\n", ans);
    }
    return 0;
}

10. UVA11624 Fire!

题目链接

题意：Joe 在迷宫工作，迷宫一部分着火了，Joe 和火每分钟移动一格，火同时向四个方向蔓延，判断Joe 是否可以在火烧他之前离开迷宫，如果能输出最早时间。

  • # 一面墙
  • . 空地
  • J Joe 最初在的空地
  • F 着火的地点

  火可能不止一个，用两个队列更新 Joe 和火的状态，每秒先更新 Joe 再更新火。

 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 <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 2e9, N = 1005;

struct node {
    int x, y;
    node(int x, int y) : x(x), y(y) {}
};

int t, r, c, vis[N][N];
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
char mp[N][N];

void bfs() {
    queue<node> jq;
    queue<node> fq;
    int time = 0;
    for (int i = 0; i < r; ++i) {
        for (int j = 0; j < c; ++j) {
            if (mp[i][j] == 'J') {
                jq.push(node(i, j));
                vis[i][j] = 1;
            }
            else if (mp[i][j] == 'F') {
                fq.push(node(i, j));
                mp[i][j] = '#';
            }
        }
    }
    while (!jq.empty()) {
        for (int i = 0, k = (int)jq.size(); i < k; ++i) {
            node now = jq.front();
            jq.pop();
            if (mp[now.x][now.y] == '#') continue;
            for (int j = 0; j < 4; ++j) {
                node nex = node(now.x + dx[j], now.y + dy[j]);
                if (nex.x >= 0 && nex.x < r && nex.y >= 0 && nex.y < c) {
                    if (mp[nex.x][nex.y] == '.' && !vis[nex.x][nex.y]) {
                        vis[nex.x][nex.y] = 1;
                        jq.push(nex);
                    }
                }
                else {
                    printf("%d\n", time + 1);
                    return;
                }
            }
        }
        for (int i = 0, k = (int)fq.size(); i < k; ++i) {
            node now = fq.front();
            fq.pop();
            for (int j = 0; j < 4; ++j) {
                node nex = node(now.x + dx[j], now.y + dy[j]);
                if (nex.x >= 0 && nex.x < r && nex.y >= 0 && nex.y < c) {
                    if (mp[nex.x][nex.y] != '#') {
                        mp[nex.x][nex.y] = '#';
                        fq.push(nex);
                    }
                }
            }
        }
        time++;
    }
    puts("IMPOSSIBLE");
}

int main() 
{
    scanf("%d", &t);
    while (t--) {
        memset(vis, 0, sizeof(vis));
        scanf("%d%d", &r, &c);
        for (int i = 0; i < r; ++i) {
            scanf("%s", mp[i]);
        }
        bfs();
    }
    return 0;
}

11. POJ3984 迷宫问题

题目链接

题意：在$5\times5$的迷宫里，1 表示墙壁，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

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 2e9;

struct node {
    int x, y;
    node (int x = 0, int y = 0) : x(x), y(y) {}
}pre[10][10];

int mp[10][10];
int vis[10][10];
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};

void bfs() {
    memset(vis, 0, sizeof(vis));
    queue<node> q;
    q.push(node(1, 1));
    while (!q.empty()) {
        node cur = q.front();
        q.pop();
        if (cur.x == 5 && cur.y == 5) return;
        for (int i = 0; i < 4; ++i) {
            node nex = node(cur.x + dx[i], cur.y + dy[i]);
            if (nex.x > 0 && nex.x <= 5 && nex.y > 0 && nex.y <= 5 && !mp[nex.x][nex.y] && !vis[nex.x][nex.y]) {
                vis[nex.x][nex.y] = 1;
                q.push(nex);
                pre[nex.x][nex.y] = cur;
            }
        }
    }
}

void print(node cur) {
    if (cur.x == 1 && cur.y == 1) {
        printf("(0, 0)\n");
        return;
    }
    print(pre[cur.x][cur.y]);
    printf("(%d, %d)\n", cur.x - 1, cur.y - 1);
}

int main() 
{
    for (int i = 1; i <= 5; ++i) {
        for (int j = 1; j <= 5; ++j) {
            scanf("%d", &mp[i][j]);
        }
    }
    bfs();
    print(node(5, 5));
    return 0;
}

12. HDU1241 Oil Deposits

题目链接

题意：$m\times n(1\le m,n\le100)$的矩形区域，“*”表示没油，“@”表示有油，石油相邻认为是一块油田，问有多少块油田。

  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
44
45
46

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 2e9, N = 105;

int d[8][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
char mp[N][N];
int n, m;

void dfs(int x, int y) {
    mp[x][y] = '*';
    for (int i = 0; i < 8; ++i) {
        int tx = x + d[i][0];
        int ty = y + d[i][1];
        if (tx >= 1 && tx <= m && ty >= 1 && ty <= n && mp[tx][ty] == '@') {
            dfs(tx, ty);
        }
    }
}

int main() 
{
    while (scanf("%d%d", &m, &n) && m) {
        for (int i = 1; i <= m; ++i) {
            scanf("%s", mp[i] + 1);
        }
        int cnt = 0;
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (mp[i][j] == '@') {
                    dfs(i, j);
                    cnt++;
                }
            }
        }
        printf("%d\n", cnt);
    }
    return 0;
}

13. HDU1495 非常可乐

题目链接

题意：给定一个 S 毫升的可乐和两个容量分别为 N 毫升和 M 毫升的杯子，在三个之间倒可乐（均没有刻度，且S ==N+M，101＞S＞0，N＞0，M＞0），问是否能平分，能请输出倒可乐的最少次数，不能输出“NO”。

  平分可乐，S 必为偶数，且为三个容器最大的两个容器平分可乐，bfs 时有 6 种倒法，可以用一些小 trick 优化。

 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

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 2e9, N = 105;

struct node {
    int v[3];
    node (int x = 0, int y = 0, int z = 0) {
        v[0] = x, v[1] = y, v[2] = z;
    }
};

int s[3], nex[3];
int step[N][N][N];

void bfs() {
    queue<node> q;
    q.push(node(s[0], 0, 0));
    step[s[0]][0][0] = 0;
    while (!q.empty()) {
        node cur = q.front();
        q.pop();
        if (cur.v[0] == cur.v[1] && cur.v[2] == 0) {
            printf("%d\n", step[cur.v[0]][cur.v[1]][cur.v[2]]);
            return;
        }
        for (int i = 0; i <= 2; ++i) {
            for (int j = 1; j <= 2; ++j) {
                for (int k = 0; k < 3; ++k) nex[k] = cur.v[k];
                int to = (i + j) % 3;
                if (cur.v[i] + cur.v[to] >= s[to]) {
                    nex[i] = cur.v[i] + cur.v[to] - s[to];
                    nex[to] = s[to];
                }
                else {
                    nex[to] = cur.v[i] + cur.v[to];
                    nex[i] = 0;
                }
                if (step[nex[0]][nex[1]][nex[2]] == -1) {
                    step[nex[0]][nex[1]][nex[2]] = step[cur.v[0]][cur.v[1]][cur.v[2]] + 1;
                    q.push(node(nex[0], nex[1], nex[2]));
                }
            }
        }
    }
    puts("NO");
}

int main() 
{
    while (scanf("%d%d%d", &s[0], &s[1], &s[2]), s[0]) {
        if (s[0] & 1) {
            puts("NO");
            continue;
        }
        if (s[1] < s[2]) swap(s[1], s[2]);
        memset(step, -1, sizeof(step));
        bfs();
    }
    return 0;
}

  也有 dalao 用数论的做法做，设两个杯子(倒出次数-倒进次数)分别为$x$和$y$，问题转化为

$$\begin{cases}\min|x|+|y|\\s.t.\quad nx+my=\displaystyle\frac{n+m}{2},\quad x,y\in \mathbb{Z},x+y\ge0\end{cases}$$

  由Bézout’s identity，

$$d=\gcd(n,m),\quad if\ \frac{n+m}{2}\%d!=0\Leftrightarrow\frac{n+m}{d}\%2!=0\Rightarrow no\ solution$$

否则令$n=ad,m=bd$，方程化为$ax+by=\displaystyle\frac{a+b}{2}$，一组简单整数解为$\displaystyle\left(\frac{1+b}{2},\frac{1-a}{2}\right)$，不定方程通解为$\displaystyle\left(\frac{1+b}{2}+kb,\frac{1-a}{2}-ka\right)$，则

$$|x|+|y|=\left|\frac{1+b}{2}+kb\right|+\left|\frac{1-a}{2}-ka\right|=\left|k+\frac{1}{2}\right|(a+b)\ge\frac{a+b}{2}$$

$\min|x|+|y|$为$\frac{a+b}{2}$，一次倒进后必有一次将瓶子中可乐倒回大瓶，倒出同理，但最后一次操作保留$\frac{n+m}{2}$毫升可乐，答案为$\frac{a+b}{2}*2-1=a+b-1=\frac{s}{d}-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

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 2e9;

int s, n, m;

int gcd(int x, int y) { return y ? gcd(y, x % y) : x; }

int main()
{
    while (scanf("%d%d%d", &s, &n, &m), s) {
        s /= gcd(n, m);
        if (s & 1) puts("NO");
        else printf("%d\n", s - 1);
    }
    return 0;
}

14. HDU2612 Find a way

题目链接

题意：y 和 m 要去 kfc 聚餐，图中有多个 kfc，求两人到达 kfc 的最少时间和。

  y 和 m 分别 bfs 即可，注意 INF 大小，因为可能有两个人都到不了的点。

 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

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 1e9, N = 205;

struct node {
    int x, y;
    node (int x = 0, int y = 0) : x(x), y(y) {}
}Y, M;

int n, m;
char mp[N][N];
int ycost[N][N], mcost[N][N], vis[N][N];
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};

void bfs(node p, int (&cost)[N][N]) {
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            vis[i][j] = 0;
            cost[i][j] = INF;
        }
    }
    queue<node> q;
    q.push(p);
    vis[p.x][p.y] = 1;
    cost[p.x][p.y] = 0;
    while (!q.empty()) {
        node now = q.front();
        q.pop();
        for (int i = 0; i < 4; ++i) {
            node nex(now.x + dx[i], now.y + dy[i]);
            if (nex.x >= 1 && nex.x <= n && nex.y >= 1 && nex.y <= m && mp[nex.x][nex.y] != '#' && !vis[nex.x][nex.y]) {
                vis[nex.x][nex.y] = 1;
                q.push(nex);
                cost[nex.x][nex.y] = cost[now.x][now.y] + 1;
            }
        }
    }
}

int main() 
{
    while (~scanf("%d%d", &n, &m)) {
        for (int i = 1; i <= n; ++i) {
            scanf("%s", mp[i] + 1);
            for (int j = 1; j <= m; ++j) {
                if (mp[i][j] == 'Y') Y = node(i, j);
                else if (mp[i][j] == 'M') M = node(i, j);
            }
        }
        bfs(Y, ycost);
        bfs(M, mcost);
        int ans = INF;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                if (mp[i][j] == '@') {
                    ans = min(ans, ycost[i][j] + mcost[i][j]);
                }
            }
        }
        printf("%d\n", ans * 11);
    }
    return 0;
}