【算法设计与分析】分支限界法习题_分支界限法印刷电路板

7-1 布线问题

印刷电路板将布线区域划分成 n×m 个方格阵列，要求确定连接方格阵列中的方格a 点到方格b 的最短布线方案。在布线时，电路只能沿直线布线，为了避免线路相交，已布了线的方格做了封锁标记，其他线路不允许穿过被封锁的方格。问线路至少穿过几个方格。下图是一个布线的例子：

输入格式:

第1行输入三个正整数，表示布线区域的尺寸n和m（2≤n,m≤100），以及被封锁的方格数k；接下来k行，每行给出两个整数x和y（1≤x≤n,1≤y≤m），表示被封锁方格的坐标（横坐标在前纵坐标在后，下同），坐标原点在左上角，并设定左上角方格坐标为(1, 1)，方格间的间距为1；最后一行输入4个整数，分别为方格a与方格b的坐标。

输出格式:

输出只有1行1个整数，为方格a到方格b的最短布线距离，若无法布线，输出-1。

输入样例:

7 7 14
1 3
1 4
2 4
3 5
4 4
4 5
5 1
5 5
6 1
6 2
6 3
7 1
7 2
7 3
3 2 4 6

输出样例:

10

提示：本题不使用分支限界法，不得分！

思路：

经典BFS/DFS走迷宫问题，注意题目样例 初始方格也算一个1个间距 因此初始化距离时为1即可

AC代码：

/*
* @Author: Spare Lin
* @Project: AcWing2022
* @Date: 2023/1/8 22:43
* @Description: 7-1 布线问题
* @URL: https://pintia.cn/problem-sets/1471841287149830144/exam/problems/1471861519453036544
*/
 
#include <bits/stdc++.h>
 
#define x first
#define y second
 
using namespace std;
 
const int N = 1e2 + 7;
const int dx[4] = {0, 1, 0, -1};
const int dy[4] = {-1, 0, 1, 0};
 
typedef pair<int, int> PII;
int n, m, k, ax, ay, bx, by;
int g[N][N], dist[N][N];
bool st[N][N];
 
int bfs() {
    queue<PII> q;
    q.push({ax, ay});
    memset(dist, -1, sizeof dist);
    dist[ax][ay] = 1; //注意题意 初始化为1
    while (!q.empty()) {
        auto t = q.front();
        q.pop();
        for (int i = 0; i < 4; i++) {
            int a = t.x + dx[i], b = t.y + dy[i];
            if (a < 1 || a > n || b < 1 || b > m) continue;
            if (st[a][b]) continue;
            dist[a][b] = dist[t.x][t.y] + 1;
            st[a][b] = true;
            q.push({a, b});
        }
    }
    return dist[bx][by];
}
 
signed main() {
    cin >> n >> m >> k;
    while (k--) {
        int x, y;
        cin >> x >> y;
        st[x][y] = true;
    }
    cin >> ax >> ay >> bx >> by;
    cout << bfs() << endl;
    return 0;
}

7-2 最少翻译

据美国动物分类学家内斯特·迈尔推算，世界上有超过100万种动物，各种动物都有自己的语言，假设动物A可以与动物B进行通信，但它不能与动物C通信，动物C只能与动物B通信，所以动物A、B之间的通信需要动物B来当翻译，问两个动物之间相互通信至少需要多少个翻译。

输入格式:

测试数据中第一行包含两个整数n（2<=n<=1000）、m（1<=m<=50000），其中n代表动物的数量，动物编号从0开始，n个动物编号为0~n-1，m表示可以相互通信动物数，接下来的m行中包含两个数字分别代表两种动物可以相互通信，在接下来包含一个整数k（k <= 20），代表查询的数量，对应每个查询包含两个数字，表示彼此通信的两个动物。

输出格式:

对于每个查询，输出这两个动物彼此通信至少需要多少个翻译，若它们之间无法通过翻译来通信，则输出-1。

输入样例:

3 2
0 1
1 2
2
0 0
0 2

输出样例:

0
1

提示：本题不使用分支限界法，不得分！

思路：

问题转化为求一个无向图中两点间的最短路径，关于最短路径算法我们可以用dijkstra、floyd、spfa、bellman-ford等等，没了解过的同学可以去了解一下，这里我写了两种方法，以下是AC代码

AC代码：

/*
* @Author: Spare Lin
* @Project: AcWing2022
* @Date: 2023/1/8 22:43
* @Description: 7-2 最少翻译
* @URL: https://pintia.cn/problem-sets/1471841287149830144/exam/problems/1471863969160429568
*/
#include <bits/stdc++.h>
 
#define x first
#define y second
 
using namespace std;
 
const int N = 1e3 + 7, M = 5e4 + 7, inf = 0x3f3f3f3f;
 
typedef pair<int, int> PII;
int n, m, k;
bool st[N], dist[N];
int h[N], e[M], ne[M], idx;
 
void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
//给定一个无向图 求两点之间是否到达 若能到达则输出最短距离 否则输出-1
//堆优化dijkstra 用spfa类似与bfs
int dijkstra(int start, int end) {
    if (start == end) return 0;
    memset(dist, 0x3f, sizeof dist);
    dist[start] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.emplace(0, start); // dist-sno
    while (!heap.empty()) {
        auto t = heap.top();
        heap.pop();
 
        int ver = t.y, distance = t.x;
        if (st[ver]) continue;
        st[ver] = true;
 
        for (int i = h[ver]; ~i; i = ne[i]) {
            int j = e[i];
            if (dist[j] > dist[ver] + 1) {
                dist[j] = dist[ver] + 1;
                heap.emplace(dist[j], j);
            }
        }
    }
    if (dist[end] == inf) return -1;
    return dist[end];
}
//spfa写法
int bfs(int start, int end) {
    queue<int> q;
    memset(dist, 0x3f, sizeof dist);
    dist[start] = 0;
    q.push(start);
    st[start] = true;
 
    while (!q.empty()) {
        auto t = q.front(); q.pop();
        st[t] = false;
        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if (dist[j] > dist[t] + 1) {
                dist[j] = dist[t] + 1;
                if (!st[j]) {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
 
    if (dist[end] == inf) return -1;
    return dist[end];
}
 
signed main() {
    cin >> n >> m;
    memset(h, -1, sizeof h);
    for (int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
        add(x, y), add(y, x);// 建无向图
    }
    cin >> k;
    while (k--) {
        int start, end;
        cin >> start >> end;
        cout << bfs(start, end) << endl;
        //cout << dijkstra(start, end) << endl;
    }
    return 0;
}

7-3 拯救安妮

原始森林中有很多危险动物，第1种是金刚(一种体型庞大的猩猩)，金刚是一种危险的动物，如果遇到金刚，必死无疑；第2种是野狗，它不会像金刚那么危险，但它会咬人，被野狗咬过两次(不管是否同一只野狗咬的)，也会死！

安妮是一个美国的女孩，她不幸迷失于原始森林中。杰克非常担心她，他要到原始森林找她。杰克能否找到一条安全的路径营救出安妮呢？

输入格式:

输入的第1行是单个数字t(0<=t<=20)，表示测试用例的数目。

每个测试用例是一个原始森林地图，第一行的整数n(0<n<=30)，表示原始森林的行数和列数，接下来n行，每行n个字符，每个字符代表的含义如下：

p表示杰克；a表示安妮；r表示道路；k表示金刚；d表示野狗。

请注意，杰克只能在上、下、左、右4个方向移动。

输出格式:

对于每个测试用例，如果杰克能够安全救出安妮，则在一行中输出“Yes”，否则在一行中输出“No”。

输入样例:

4
3
pkk
rrd
rda
3
prr
kkk
rra
4
prrr
rrrr
rrrr
arrr
5
prrrr
ddddd
ddddd
rrrrr
rrrra

输出样例:

Yes
No
Yes
No

提示：本题不使用分支限界法，不得分！

思路：

同样是BFS走迷宫问题，不同的是注意附带的被野狗咬的次数不能超过2次，我们用一个dist数组记录走到每个位置时被野狗咬的次数即可，然后在扩展时我们遇到野狗特判即可

AC代码：

/*
* @Author: Spare Lin
* @Project: AcWing2022
* @Date: 2023/1/8 22:43
* @Description: 7-3 拯救安妮
* @URL: https://pintia.cn/problem-sets/1471841287149830144/exam/problems/1471863969160429568
*/
#include <bits/stdc++.h>
 
#define x first
#define y second
 
using namespace std;
 
const int N = 35;
const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
typedef pair<int, int> PII;
int t, n, sx, sy, ex, ey;
bool st[N][N];
char g[N][N];
int dist[N][N]; //记录被咬次数
 
bool bfs() {
    queue<PII> q;
    q.emplace(sx, sy);
    st[sx][sy] = true;
    while (!q.empty()) {
        auto t = q.front();
        q.pop();
        if (t.x == ex && t.y == ey) return true;
        for (int i = 0; i < 4; i++) {
            int a = t.x + dx[i], b = t.y + dy[i];
            if (a < 1 || a > n || b < 1 || b > n) continue;
            if (g[a][b] == 'k' || st[a][b]) continue;
            if (g[a][b] == 'd' && dist[t.x][t.y] == 1) continue;
            //此时已经不能再被狗咬
            st[a][b] = true;
            if (g[a][b] == 'd') dist[a][b] = dist[t.x][t.y] + 1;
            q.emplace(a, b);
        }
    }
    return false;
}
 
signed main() {
    cin >> t;
    while (t--) {
        cin >> n;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                cin >> g[i][j];
                if (g[i][j] == 'p') sx = i, sy = j;
                if (g[i][j] == 'a') ex = i, ey = j;
            }
        }
        memset(st, 0, sizeof st);
        memset(dist, 0, sizeof dist);
        bfs() ? puts("Yes") : puts("No");
    }
    return 0;
}

7-4 饥饿的章鱼 (小数据版本)

作者 J.Liau单位 泉州师范学院

小易总是感觉饥饿，所以作为章鱼的小易经常出去寻找贝壳吃。最开始小易在一个初始位置x_0。对于小易所处的当前位置x，他只能通过神秘的力量移动到 4 * x + 3或者8 * x + 7。因为使用神秘力量要耗费太多体力，所以它只能使用神秘力量最多20次。贝壳总生长在能被17整除的位置(比如：位置0、17、34、51、……)。小易需要你帮忙计算最少需要使用多少次神秘力量就能吃到贝壳。

输入格式:

输入有多组测试用例，每组用例输入一个初始位置x0,范围在1到1,000,000,000。

输出格式:

对每组用例输出小易最少需要使用神秘力量的次数，如果使用次数使用完还没找到贝壳，则输出-1。

输入样例:

100
200

输出样例:

2
-1

提示：

如果不采用分支限界法，本题不得分！

思路：

BFS迭代 两种情况 开一个哈希表来记录访问的点 用来减少迭代次数

AC代码：

#include <bits/stdc++.h>
 
#define x first
#define y second
#define int long long
 
using namespace std;
 
typedef pair<int, int> PII;
const int mod = 1e9 + 7, inf = 1e9 + 7;
 
int x;
 
int bfs(int x) {
    if (x < 1 || x >= inf) return -1;
    x %= mod;
    queue<PII> q;
    unordered_map<int, int> vis;//哈希表记录是否被访问过 减少迭代次数
    q.emplace(x, 0); // num - cnt
    while (!q.empty()) {
        auto t = q.front();
        q.pop();
        if (t.x % 17 == 0) return t.y;
        if (t.y < 20) {
            auto cur1 = t, cur2 = t;
            cur1.x = (4 * t.x + 3) % mod, cur1.y = t.y + 1;
            cur2.x = (8 * t.x + 7) % mod, cur2.y = t.y + 1;
            if (!vis.count(cur1.x)) {
                vis[cur1.x] = 1;
                q.emplace(cur1);
            }
            if (!vis.count(cur2.x)) {
                vis[cur2.x] = 1;
                q.emplace(cur2);
            }
        }
    }
    return -1;
}
 
signed main() {
    while (cin >> x) cout << bfs(x) << endl;
    return 0;
}

原题来源：网易2017内推笔试编程题-饥饿的小易

注：本题是老师把原题数据改小后发布的，原题数据量很大，BFS迭代若不开哈希表会爆内存。

原题AC代码：

#include <bits/stdc++.h>
 
#define x first
#define y second
#define int long long
 
using namespace std;
 
typedef pair<int, int> PII;
const int mod = 1e9 + 7, inf = 1e9 + 7;
 
int n, x;
 
int bfs(int x) {
    if (x < 1 || x >= inf) return -1;
    x %= mod;
    queue<PII> q;
    unordered_map<int, int> vis;
    q.emplace(x, 0); // num - cnt
    while (!q.empty()) {
        auto t = q.front();
        q.pop();
        if (t.x % mod == 0) return t.y;
        if (t.y < 1e5) {
            auto cur1 = t, cur2 = t;
            cur1.x = (4 * t.x + 3) % mod, cur1.y = t.y + 1;
            cur2.x = (8 * t.x + 7) % mod, cur2.y = t.y + 1;
            if (!vis.count(cur1.x)) {
                vis[cur1.x] = 1;
                q.emplace(cur1);
            }
            if (!vis.count(cur2.x)) {
                vis[cur2.x] = 1;
                q.emplace(cur2);
            }
        }
    }
    return -1;
}
 
signed main() {
    while (cin >> x) {
        cout << bfs(x) << endl;
    }
    return 0;
}

7-5 机器的重量

设某一机器由n个部件组成,部件编号为1~n，每一种部件都可以从m个不同的供应商处购得，供应商编号为1~m。设wij是从供应商j处购得的部件i的重量，cij是相应的价格。对于给定的机器部件重量和机器部件价格，计算总价格不超过d的最小重量机器设计。

输入格式:

第1行输入3个正整数n,m和d（1≤n、m≤20，1≤d≤100）。接下来n行输入wij（每行m个整数，且1≤wij≤10），最后n行输入cij（每行m个整数，且1≤cij≤50）。

输出格式:

输出的第1行包括n个整数，表示每个部件（按1~n的顺序）在对应编号的供应商处购得，第2行为对应的最小重量。

输入样例:

3 3 7
1 2 3
3 2 1
2 3 2
1 2 3
5 4 2
2 1 2

输出样例:

1 3 1
4

提示：

如果不采用分支限界法，本题不得分！

思路：

dfs深搜，回溯

AC代码：

#include <iostream>
#include <cstring>
#include <algorithm>
 
using namespace std;
 
const int N = 1e2 + 7;
 
int n, m, d, res = 0x3f3f3f3f, curw, curc;
int w[N][N], c[N][N], ans[N], sale[N];
 
void dfs(int u) {
    if (u > n) { //搜索结束
        res = curw; //更新最小重量
        for (int j = 1; j <= n; j++) ans[j] = sale[j];
    } else {
        for (int j = 1; j <= m; j++) {
            if (curc + c[u][j] <= d && curw + w[u][j] < res) {
                sale[u] = j;
                curc += c[u][j], curw += w[u][j];
                dfs(u + 1);
                curc -= c[u][j], curw -= w[u][j]; //回溯
            }
        }
    }
}
 
signed main() {
    cin >> n >> m >> d;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> w[i][j];//wij是从供应商j处购得的部件i的重量
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> c[i][j]; //cij是相应的价格
        }
    }
    dfs(1);
    for (int i = 1; i <= n; i++) {
        cout << ans[i] << ' ';
    }
    cout << endl;
    cout << res << endl;
    return 0;
}

7-2 马走日

作者 J.Liau单位 泉州师范学院

在m行n列的中国象棋棋盘上，马在左下角处，马走日字，且假设只能往右走（右上或右下），求从起点到右上角处有几种不同的走法、最快走法的步数以及方案。注意，m行n列的棋盘，若左下角坐标是(1, 1)，则右上角坐标是(n, m)。

输入格式:

输入有多个用例，每个用例包括1行，各有两个整数m, n（1≤m, n≤20），以输入m=0、n=0结束。

输出格式:

对输入中的每组测试数据，输出2行，第1行1个数字表示从起点(1, 1)到右上角(n, m)处总共不同的走法数；第2行第1个数字输出最快走法的步数；接下来输出最快走法的方案（输出格式见样例），如果存在多个答案输出第1个满足条件结果（为确保答案的唯一性，请按下图的顺序扩展点）。如无法到达终点，只需要输出-1。

输入样例:

4 4
6 4
0 0

输出样例:

2
2: [1,1]->[3,2]->[4,4]
-1

提示：

如果不采用分支限界法，本题不得分！

思路：dfs求方案数 ，bfs求最短路径，开一个二维PII存扩展到每个点的前驱用来打印路径，注意题目右上角为（m,n）与输入是相反的，这题找bug找了几个小时~

AC代码：

（没法测了不知道能不能AC）

#include <bits/stdc++.h>
 
#define x first
#define y second
 
using namespace std;
 
typedef pair<int, int> PII;
const int N = 30, dx[4] = {1, 2, 2, 1}, dy[4] = {-2, -1, 1, 2}; //按照图中顺序扩展
const int inf = 0x3f3f3f3f;
int n, m, res;
int dist[N][N];
bool st[N][N], vis[N][N];
PII pre[N][N];
 
void dfs(int x, int y) { //求方案数
    vis[x][y] = true;
    if (x == n && y == m) {
        res++;
        return;
    }
 
    for (int i = 0; i < 4; i++) {
        int a = x + dx[i], b = y + dy[i];
        if (a < 1 || a > n || b < 1 || b > m) continue;
        vis[x][y] = true;
        dfs(a, b);
        vis[x][y] = false;
    }
}
 
void bfs() { //迭代求最快的走法
    queue<PII> q;
    q.emplace(1, 1);
    memset(st, 0, sizeof st);
    memset(dist, 0x3f, sizeof dist);
    memset(pre, -1, sizeof pre);
 
    st[1][1] = true;
    dist[1][1] = 0;
    pre[1][1] = {m, n};
 
    while (!q.empty()) {
        auto t = q.front();
        q.pop();
        for (int i = 0; i < 4; i++) {
            int a = t.x + dx[i], b = t.y + dy[i];
            if (a < 1 || a > n || b < 1 || b > m) continue;
            if (st[a][b]) continue;
            if (pre[a][b].x != -1) continue;
            st[a][b] = true;
            dist[a][b] = dist[t.x][t.y] + 1;
            pre[a][b] = t;
            q.emplace(a, b);
        }
    }
}
 
string get(int x, int y) {
    return "[" + to_string(x) + "," + to_string(y) + "]";
}
 
vector<string> ans;
 
void getRoad() {
    PII end = {m, n};
    while (true) {
        ans.push_back(get(end.x, end.y));
        if (end.x == 1 && end.y == 1) break;
        end = pre[end.x][end.y];
    }
}
 
signed main() {
    while (cin >> n >> m && n , m) {
        bfs();
        if (dist[m][n] == inf) {
            cout << -1 << endl;
        } else {
            res = 0;
            memset(vis, 0, sizeof vis);
            dfs(1, 1);
            cout << res << endl; //方案数
            getRoad();
            cout << dist[m][n] << ": "; //最短路径
            for (int i = ans.size() - 1; i >= 0; i--) {
                if (i != 0) cout << ans[i] << "->";
                else cout << ans[i];
            }
            ans.clear();
            cout << endl;
        }
    }
    return 0;
}