kuangbin专题

专题一 简单搜索

1. 棋盘问题

思路

n皇后裸体

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
using namespace std;

const int N = 10;
int n, k;
char a[N][N];
int dfs(int i, int mark, int x) {
    if (i == n ) return x == 0;
    int ans = dfs(i + 1, mark, x);
    for (int j = 0; j < n; j ++) {
        if (a[i][j] == '.' || (mark & (1 << j))) continue;
        ans += dfs(i + 1, mark | (1 << j), x - 1);
    }
    return ans;
}
int main() {
    while (cin >> n >> k, n != -1 && k != -1) {
        for (int i = 0; i < n; i ++) cin >> a[i];
        cout << dfs(0, 0, k) << endl;
    }
    return 0;
}

2.Dungeon Master POJ - 2251

身陷三层迷宫，可上下前后左右走，问从S到E到最小路径。从二维BFS到三维BFS到转换，代码不变。

要注意POJ使用C98，不支持C++11的特性

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 <iostream>
#include <cstring>
#include <queue>

using namespace std;

const int N = 35;
bool g[N][N][N], vis[N][N][N];
int n, m, l;
int sx, sy, sz;
int ex, ey, ez;

int dirs[][3]  = {0, 0, -1, 0, 0, 1, 0, -1, 0, 0, 1, 0, 1, 0, 0, -1, 0, 0};
struct Node{
    int x, y, z;
    Node(int a, int b, int c):x(a), y(b), z(c) {
    }
};

int solve() {
    queue<Node> q;
    q.push(Node(sx, sy, sz));
    g[sx][sy][sz] = false;
    int res = 0;
    while (q.size()) {
        int size = q.size();
        for (int i = 0; i < size; i ++) {
            Node t = q.front(); q.pop();
            if (t.x == ex && t.y == ey && t.z == ez) return res;
            for (int i = 0; i < 6; i ++) {
                int tx = t.x + dirs[i][0], ty = t.y + dirs[i][1], tz = t.z + dirs[i][2];
                if (tx >= n || tx < 0 || ty >= m || ty < 0 || tz >= l || tz < 0 || !g[tx][ty][tz]) continue;
                g[tx][ty][tz] = false;
                q.push(Node(tx, ty, tz));
            }
        }
        ++ res;
    }
    return -1;
}

int main() {
    while(cin >> n >> m >> l, n && m && l) {
        char ch;
        memset(g, false, sizeof g);
        for (int i = 0; i < n; i ++) {
            for (int j = 0; j < m; j ++) {
                for (int k = 0; k < l; k ++) {
                    cin >> ch;
                    if (ch == 'S') sx = i, sy = j, sz = k;
                    if (ch == 'E')  ex = i, ey = j, ez = k;
                    g[i][j][k] = ch != '#';
                }
            }
            getchar();
        }
        int res = solve();
        printf(res == - 1 ? "Trapped!\n" : "Escaped in %d minute(s).\n", res);
    }
    return 0;
}

3.POJ-3278 Catch That Cow

给定数字n和k，从n出发，每次可以-1、+1、*2，问变成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
#include <iostream>
#include <queue>
#include <set>
using namespace std;

const int N = 200005;
int n, k;
queue<int> q;
bool vis[N];

void cal(int x) {
    if (x < 0 || x >= N || vis[x]) return;
    q.push(x);
}

int solve() {
    q.push(n);
    int res = 0;
    while (q.size()) {
        int size = q.size();
        for (int i = 0; i < size; i ++) {
            int t = q.front(); q.pop();
            vis[t] = true;
            if (t == k) return res;
            cal(t + 1);
            cal(t - 1);
            cal(t * 2);
        }
        ++res;   
    }
    return -1;
}

int main() {
    cin >> n >> k;
    cout << solve() << endl;
    return 0;
}

4.POJ - 3279 Fliptile

有N*M的格子，格子一边是黑色，一边是白色可以任意翻转，翻转一个格子会触发上下左右四个格子同时翻转。给定初始状态，求翻转为全部白色格子所需要的最小步骤，若有多个翻转方案，输出字典序最小的一个

思路：二进制枚举第一列的所有翻转的方案，后续列由于受到前一列的翻转方案约束是固定的要维护前一列的颜色，可以推到而来。具体的，

  1. 若前一列当前格子为黑色，则当前列当前格子需要翻转使得上一个格子可以触发翻转成白色，依次类推若最后一列无法
  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
74
75
76
77
78
79
80
81
82
83
84
85
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 20, M = 20;
int n, m;
bool g[N][M], turn[N][N], arr[N][N], ret[N][N];
int dirs[][2] = {0, -1, 0, 1, 1, 0, -1, 0};

int solve(int x) {
    //重置翻转次数
    memset(turn, 0, sizeof turn);
    for (int i = 0; i < m; i ++) 
        turn[1][i + 1] = x & (1 << i);
    //拷贝副本，用作当次计算的数组
    memset(arr, 0, sizeof arr);
    for (int i = 1; i <= n; i ++) 
        for (int j = 1; j <= m; j++) 
            arr[i][j] = g[i][j];
    //计算当前第一列的翻转情况是x时，推演剩下的列的翻转情况
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= m; j ++) {
            if (i != 1 && arr[i - 1][j])
                turn[i][j] = 1;
            if (turn[i][j]) {
                arr[i][j] = !arr[i][j];
                for (int k = 0; k < 4; k ++) {
                    int x = i + dirs[k][0];
                    int y = j + dirs[k][1];
                    arr[x][y] = !arr[x][y];
                }
            }
        }

    bool flag = true;
    for (int i = 1; i <= m; i ++) 
        if (arr[n][i]) {
            flag = false;
            break;
        }
    if (!flag) return -1;
    int res = 0;
    for (int i = 1; i <= n; i ++) 
        for (int j = 1; j <= m; j ++)
            res += turn[i][j];
    return res;
}

void copy() {
    for (int i = 1; i <= n; i ++) 
        for (int j = 1; j <= m; j ++)
            ret[i][j] = turn[i][j];
}
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i ++) 
        for (int j = 1; j <= m; j ++) 
            cin >> g[i][j];

    int min_res = 0x3f3f3f3f;
    bool flag = false;
  	// 枚举第一列的所有翻转可能
    for (int i = 0; i < (1 << m); i ++) {
        int res = solve(i);
        if (res != -1 && res < min_res) {
            flag = 1;
            min_res = res;
            copy();
        }
    }

    if (flag) {
        for (int i = 1; i <= n; i ++) {
            for (int j = 1; j <= m; j ++) {
                cout << ret[i][j] << " ";
            }
            puts("");
        }
    } else {
        cout << "IMPOSSIBLE" << endl;
    }
    return 0;
}

5.POJ-1426

Find The Multiple

给点n，求任意能整整除n且只包含数字1和0的一个数

bfs所有数位上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
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

typedef unsigned long long ull;
ull n;

ull solve() {
    queue<ull> q;
    q.push(1);
    while (q.size()) {
        ull t = q.front(); q.pop();
        if (t % n == 0) return t;
        q.push(t * 10);
        q.push(t * 10 + 1);
    }
    return -1;
}

int main() { 
    while (cin >> n, n) {
        cout << solve() << endl;
    }
    return 0;
}

6.POJ - 3126

Prime Path

有n组数据，每组输出给出两个四位质数a b，每次可以将一位上的数字变换，求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
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
typedef unsigned long long ull;

int n;
int a, b;
const int N = 10005;
bool prime[N];  // 素数表
bool vis[N];    // 访问标记
int bases[] = {1, 10, 100, 1000};

int solve() {
    // 重置访问标记
    memset(vis, 0, sizeof vis);
    queue<int> q;
    // 加入bfs起点
    q.push(a);
    vis[a] = 1;
    int ans = 0;
    // bfs
    while (q.size()) {
        int len = q.size();
        while (len --) {
            int t = q.front(); q.pop();
            // 找到目标，返回路径值
            if (t == b) return ans;
            for (int i = 0; i < 4; i ++) {
                int base = bases[i];
                int n1 = (t / base / 10) * base * 10;
                int n2 = t % base;
                for (int ch = 0; ch <= 9; ch ++) {
                    int n3 = ch * base;
                    int num = n1 + n2 + n3;
                    if (!prime[num] || vis[num]) continue;
                    vis[num] = 1;
                    q.push(num);
                }
                // cout << endl;
            }
        }
        ++ ans;
    }
    return -1;
}

int main() { 
    // 素数打表
    for (int i = 1000; i < 10000; i++) {
        bool flag = true;
        for (int j = 2; j * j <= i; j ++)
            if (i % j == 0) {
                flag = false;
                break;
            }
        prime[i] = flag;
    }
    // 输入输出
    cin >> n;
    while (n--) {
        cin >> a >> b;
        cout << solve() << endl;
    }
    return 0;
}

7.POJ-3087

Shuffle’m Up

两手扑克牌，s2第一张，s1第二张交替洗，然后对半分，问能否洗成S12的牌，可以输出次数，否则输出-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
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
typedef unsigned long long ull;

const int N = 105;
string s1, s2, s;
int T, n;

int dfs(string a, string b, int step) {
    if (a + b == s) return step;
    string tmp = "";
    for (int i = 0; i < n; i ++) tmp = tmp + b[i] + a[i];
    a = tmp.substr(0, n);
    b = tmp.substr(n, n);
    if (a.compare(s1) == 0 && b.compare(s2) == 0) return -1;
    return dfs(a, b, step + 1);
}

int solve() {
    return dfs(s1, s2, 0);
}

int main() { 
    cin >> T;
    for (int i = 1; i <= T; i ++) {
        cin >> n;
        cin >> s1 >> s2 >> s;
        printf("%d %d\n", i, solve());
    }
    return 0;
}

8. POJ-3414

Pots

刷题

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！