信息学奥赛-一本通-第二部分 基础算法 --＞ 第五章 搜索与回溯算法

1317：【例5.2】组合的输出
【题目描述】
排列与组合是常用的数学方法，其中组合就是从n个元素中抽出r个元素(不分顺序且r≤n)，我们可以简单地将n个元素理解为自然数1，2，…，n，从中任取r个数。

现要求你用递归的方法输出所有组合。

例如n＝5，r＝3，所有组合为：

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

【题目分析】

【代码实现】
#include <bits/stdc++.h>
 
using namespace std;
 
bool vis[21];
int n;
void dfs(int b, int r) {  //r 控制循环层数  b控制循环起点
    if (r == 0) {
        for (int i = 1; i <= n; i++)
            if (vis[i]) cout << "  " << i ;
        cout << endl;
        return ;
    };
 
    for (int i = b; i <= n; i++) {
        if (vis[i] == 0) {
            vis[i] = 1;
            dfs(i + 1, r - 1);
            vis[i] = 0;
        }
    }
}
int main() {
    //input data
    int  r;
    cin >> n >> r;
    dfs(1, r);
    return 0;
}

1318：【例5.3】自然数的拆分
【题目描述】
任何一个大于1的自然数n，总可以拆分成若干个小于n的自然数之和。

当n=7共14种拆分方法：

【题目分析】

 【代码实现】
#include <bits/stdc++.h>
 
using namespace std;
 
int n;
int a[100005];
int sum = 0;
void dfs(int m, int index) {
    if (sum > n) return;
    if (sum == n) {
        cout << n << "=";
        cout << a[1];
        for (int i = 2; i < index; i++) {
            cout << "+" << a[i];
        }
        cout << endl;
        return;
    }
    for (int i = m; i < n; i++) {
        a[index] = i;
        sum += i;
        dfs(i, index + 1);
        sum -= i;
    }
}
int main() {
    //input data
    cin >> n;
    dfs(1, 1);
    return 0;
}

1212：LETTERS
【题目描述】
给出一个roe×col的大写字母矩阵，一开始的位置为左上角，你可以向上下左右四个方向移动，并且不能移向曾经经过的字母。问最多可以经过几个字母。

【题目分析】

 【代码实现】
#include <bits/stdc++.h>
 
using namespace std;
 
int n, m;
char a[25][25];
bool vis[30];
int maxc = 0;
int _next[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
void dfs(int i, int j, int cnt) {
    maxc = max(cnt, maxc);
    for (int k = 0; k <= 3; k++) {
        int x = i + _next[k][0];
        int y = j + _next[k][1];
        if (x < 0 || y < 0 || x >= n || y >= m) continue;
        if (vis[a[x][y] - 'A']) continue;
        vis[a[x][y] - 'A'] = 1;
        dfs(x, y, cnt + 1);
        vis[a[x][y] - 'A'] = 0;
    }
}
int main() {
    //input data
    cin >> n >> m;
    getchar();
    for (int i = 0; i < n; i++) {
        cin.getline(a[i], 25);
    }
    vis[a[0][0] - 'A'] = 1;
    maxc++;
    dfs(0, 0, 1);
    cout << maxc;
    return 0;
}

1213：八皇后问题
【题目描述】
在国际象棋棋盘上放置八个皇后，要求每两个皇后之间不能直接吃掉对方。

【题目分析】

【代码实现】
#include <bits/stdc++.h>
 
using namespace std;
#define N 105
int a[N][N], b[N];
int vis[N][N];
int s;
void dfs(int step) {
    if (step == 8 + 1) {
        s++;
        for (int i = 1; i <= 8; i++)
            a[s][i] = b[i];
        return;
    }
    for (int i = 1; i <= 8; i++) {
        if (vis[0][i] == 0 && vis[1][step + i] == 0 && vis[2][step - i + 8] == 0) {
            vis[0][i] = 1;
            vis[1][i + step] = 1;
            vis[2][step - i + 8] = 1;
            b[step] = i;
 
            dfs(step + 1);
 
            vis[0][i] = 0;
            vis[1][i + step] = 0;
            vis[2][step - i + 8] = 0;
        }
    }
}
 
int main() {
    dfs(1);
    for (int t = 1; t <= s; t++) {
        printf("No. %d\n", t);
        for (int i = 1; i <= 8; i++) {
            for (int j = 1; j <= 8; j++) {
                if (a[t][j] == i) cout << "1 ";
                else cout << "0 ";
            }
            cout << endl;
        }
    }
    return 0;
}
1214：八皇后
【题目描述】
会下国际象棋的人都很清楚：皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将8个皇后放在棋盘上（有8 × 8个方格），使它们谁也不能被吃掉！这就是著名的八皇后问题。

对于某个满足要求的8皇后的摆放方法，定义一个皇后串a与之对应，即a=b1b2...b8，其中bi为相应摆法中第i行皇后所处的列数。已经知道8皇后问题一共有92组解（即92个不同的皇后串）。

给出一个数b，要求输出第b个串。串的比较是这样的：皇后串x置于皇后串y之前，当且仅当将x视为整数时比y小。

【题目分析】

【代码实现】
#include <bits/stdc++.h>
 
using namespace std;
 
int n = 8;
bool a[9][9];
int _count = 0;
int b[93][8];
void dfs(int m) {
    if (m == 9) {
//        printf("No. %d\n", ++_count);
        _count++;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (a[j][i] == 1) b[_count][j] = i;
//                printf("%d ", a[j][i]);
            }
//            printf("\n");
        }
        return;
    }
    for (int i = 1; i <= n; i++) {  //第m行 第i列
        bool flag = 1;
        for (int j = 1; j <= n; j++) {
            for (int k = 1; k <= n; k++) {
                if (k == i && a[j][k] == 1) flag = 0;
                if (j - k == m - i && a[j][k] == 1) flag = 0;
                if (j + k == m + i && a[j][k] == 1) flag = 0;
                if (flag == 0) break;
            }
        }
        if (flag) {
            a[m][i] = 1;
            dfs(m + 1);
            a[m][i] = 0;
        } else continue;
    }
}
int main() {
    //input data
    dfs(1);
    int m;
    cin >> m;
    while (m--) {
        int k;
        cin >> k;
        for (int i = 1; i <= n; i++) {
            printf("%d", b[k][i]);
        }
        printf("\n");
    }
    return 0;
}

1215：迷宫
【题目描述】
一天Extense在森林里探险的时候不小心走入了一个迷宫，迷宫可以看成是由n×n的格点组成，每个格点只有22种状态，.和#，前者表示可以通行后者表示不能通行。同时当Extense处在某个格点时，他只能移动到东南西北(或者说上下左右)四个方向之一的相邻格点上，Extense想要从点A走到点B，问在不走出迷宫的情况下能不能办到。如果起点或者终点有一个不能通行(为#)，则看成无法办到。

【题目分析】

 【代码实现】
#include <bits/stdc++.h>
 
using namespace std;
 
int n, k;
int _next[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
char a[105][105];
bool vis[105][105];
int sx, sy, ex, ey;
bool flag = 0;
void dfs(int x, int y) {
    if (x == ex && y == ey) flag = 1;
    for (int i = 0; i <= 3; i++) {
        int nx = x + _next[i][0];
        int ny = y + _next[i][1];
        if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
        if (vis[nx][ny] == 1 || a[nx][ny] == '#') continue;
        vis[nx][ny] = 1;
        dfs(nx, ny);
//        vis[nx][ny] = 0;
    }
}
int main() {
    //input data
    cin >> k;
    while (k--) {
        cin >> n;
        flag = 0;
        memset(vis, 0, sizeof(vis));
        for (int i = 0; i < n; i++) {
            getchar();
            for (int j = 0; j < n; j++) {
                scanf("%c", &a[i][j]);
            }
        }
        cin >> sx >> sy >> ex >> ey;
        vis[sx][sy] = 1;
        dfs(sx, sy);
        if (flag) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
 
    return 0;
}

1216：红与黑
【题目描述】
有一间长方形的房子，地上铺了红色、黑色两种颜色的正方形瓷砖。你站在其中一块黑色的瓷砖上，只能向相邻的黑色瓷砖移动。请写一个程序，计算你总共能够到达多少块黑色的瓷砖。

【题目分析】

 【代码实现】
#include <bits/stdc++.h>
 
using namespace std;
 
int m, n;
int _next[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
char a[105][105];
//string a[105];
bool vis[105][105];
int sx, sy;
int sum = 0;
//void print() {
//    cout << "************************" << endl;
//    for (int i = 0; i < n; i++) {
//        for (int j = 0; j < m; j++) {
//            cout << a[i][j] << " ";
//        }
//        cout << endl;
//    }
//}
void dfs(int x, int y) {
    for (int i = 0; i <= 3; i++) {
        int nx = x + _next[i][0];
        int ny = y + _next[i][1];
        if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
        if (vis[nx][ny] == 1 || a[nx][ny] == '#') continue;
        vis[nx][ny] = 1;
        sum++;
        dfs(nx, ny);
//        print();
    }
}
int main() {
    //input data
    while (cin >> m >> n, m + n != 0) {
        memset(vis, 0, sizeof(vis));
        sum = 0;
        for (int i = 0; i < n; i++) {
            getchar();
            for (int j = 0; j < m; j++) {
                scanf("%c", &a[i][j]);
                if (a[i][j] == '@') sx = i, sy = j;
            }
        }
//        print();
        vis[sx][sy] = 1;
        sum++;
        dfs(sx, sy);
        cout << sum << endl;
    }
 
    return 0;
}

 1217：棋盘问题
【题目描述】
在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放 k个棋子的所有可行的摆放方案 C。

【题目分析】

 【代码实现】
#include <bits/stdc++.h>
 
using namespace std;
 
int n, k;
int sum = 0;
string a[10];
bool vis[10];
 
void dfs(int m, int row) {
    for (int i = row; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (a[i][j] == '.' || vis[j] == 1) continue;
            vis[j] = 1;
            if (m == k) sum++;
            else  dfs(m + 1, i + 1);
            vis[j] = 0;
        }
    }
}
int main() {
    //input data
    while (cin >> n >> k, n != -1) {
        sum = 0;
        memset(vis, 0, sizeof(vis));
        for (int i = 0; i < n; i++) {
            cin >> a[i];
//            cout<<a[i]<<endl;
        }
        dfs(1, 0);
        cout << sum << endl;
    }
    return 0;
}
1218：取石子游戏
【题目描述】
有两堆石子,两个人轮流去取。每次取的时候,只能从较多的那堆石子里取,并且取的数目必须是较少的那堆石子数目的整数倍，最后谁能够把一堆石子取空谁就算赢。

比如初始的时候两堆石子的数目是25和7。

25 7    -->    11 7    -->    4 7    -->    4 3    -->    1 3    -->    1 0
选手1取        选手2取        选手1取        选手2取        选手1取
最后选手1（先取的）获胜，在取的过程中选手2都只有唯一的一种取法。

给定初始时石子的数目，如果两个人都采取最优策略，请问先手能否获胜。

【题目分析】

【代码实现】
#include <bits/stdc++.h>
 
using namespace std;
 
 
bool check(int m, int n) {
    if (m < n) swap(m, n);
    if (m / n >= 2) return true;
    else return !check(m - n, n);
}
 
int main() {
    //input data
    int m, n;
    while (cin >> m >> n, m + n != 0) {
        if (check(m, n)) cout << "win" << endl;
        else cout << "lose" << endl;
    }
 
    return 0;
}
1219：马走日
【题目描述】
马在中国象棋以日字形规则移动。

请编写一段程序，给定n×m大小的棋盘，以及马的初始位置(x，y)，要求不能重复经过棋盘上的同一个点，计算马可以有多少途径遍历棋盘上的所有点。

【题目分析】

【代码实现】
#include <bits/stdc++.h>
 
using namespace std;
 
int m, n;
bool vis[15][15];
int _next[8][2] = {{1, 2}, {1, -2}, {-1, 2}, {-1, -2}, {2, 1}, {2, -1}, {-2, 1}, {-2, -1}};
int sum = 0;
int ans = 0;
void dfs(int x, int y) {
    for (int i = 0; i < 8; i++) {
        int nx = x + _next[i][0];
        int ny = y + _next[i][1];
        if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
        if (vis[nx][ny] == 1) continue;
        vis[nx][ny] = 1;
        sum++;
        if (sum == m * n) ans++;
        else dfs(nx, ny);
        sum--;
        vis[nx][ny] = 0;
    }
}
int main() {
    //input data
    int k;
    cin >> k;
    while (k--) {
        int x, y;
        cin >> m >> n >> x >> y;
        sum = ans = 0;
        memset(vis, 0, sizeof(vis));
        vis[x][y] = 1;
        sum++;
        dfs(x, y);
        cout << ans << endl;
    }
    return 0;
}
1220：单词接龙
【题目描述】
单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”（每个单词都最多在“龙”中出现两次），在两个单词相连时，其重合部分合为一部分，例如beast和astonish，如果接成一条龙则变为beastonish，另外相邻的两部分不能存在包含关系，例如at和atide间不能相连。

【题目分析】

 【代码实现】
#include <bits/stdc++.h>
 
using namespace std;
 
int n;
string str;
//int len = 0;
string a[25];
int num[25];
int maxlen = 0;
 
 
int check(string s, string e) { //返回重复的个数
    int ls = min(s.size(), e.size());
    for (int i = 1; i < ls; i++) {
        if (s.substr(s.size() - i, s.size()) == e.substr(0, i)) return i;
    }
    return 0;
}
 
void dfs(int p, int len) {
    maxlen = max(maxlen, len);
    for (int i = 0; i < n; i++) {
        int k = check(a[p], a[i]);
        if (num[i] == 0 || k == 0) continue; //单词用完 不能拼接
        num[i]--;
        dfs(i, len + a[i].size() - k);
        num[i]++;
    }
}
int main() {
    //input data
    cin >> n;
    for (int i = 0; i <= n; i++) {  //read data and init
        cin >> a[i];
        num[i] = 2;
    }
 
    for (int i = 0; i < n; i++) {
        if (a[i][0] == a[n][0]) {
            num[i]--;
            dfs(i, a[i].size());
            num[i]++;
        }
    }
    cout << maxlen;
    return 0;
}
1221：分成互质组
【题目描述】
给定n个正整数，将它们分组，使得每组中任意两个数互质。至少要分成多少个组？

【题目分析】

 【代码实现】
#include <bits/stdc++.h>
 
using namespace std;
 
 
int ans = 1e9;
int d[15], group[15];
int n;
 
int gcd(int a, int b) {
    if (b == 0) return a;
    else return gcd(b, a % b);
}
 
void dfs(int pos, int cnt) {
    int i = 1;
    for (i = 1; i <= cnt + 1; i++) { //group的标号
        int j = 1;
        for (j = 1; j < pos; j++) {  //没有标号或者有互质组 j==pos
            if (group[j] == i && gcd(d[j], d[pos]) > 1)
                break;
        }
        if (j ==  pos) {
            group[pos] = i;
            int flag = 0;
            if (i > cnt) flag = 1;
            if (pos == n)
                ans = min(ans, cnt + flag);
            else
                dfs(pos + 1, cnt + flag);
        }
    }
}
int main() {
    //input data
    cin >> n;
    for (int i = 1; i <= n; i++)cin >> d[i];
    group[1] = 1;
    dfs(2, 1);
    cout << ans;
    return 0;
}
1222：放苹果
【题目描述】
把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？（用K表示）5，1，1和1，5，1 是同一种分法。

【题目分析】

 【代码实现】
#include <bits/stdc++.h>
 
using namespace std;
int m, n;
int ans;
int sum = 0;
int a[15];
void print() {
    for (int j = 1; j <= n; j++) {
        cout << a[j] << " ";
    }
    cout << endl;
}
void dfs(int _m, int _n) {
    for (int i = _m; i <= m; i++) {     //枚举情况
        if (sum + i <= m && _n <= n) {  //满足条件
            sum += i;                   //保存结果
            if (_n == n && sum == m) ans++; //达到目的地
            else dfs(i, _n + 1);
            sum -= i;                   //恢复状态
        }
    }
}
int main() {
    //input data
    int t;
    cin >> t;
    while (t--) {
        cin >> m >> n;
        ans = 0;
        sum = 0;
        memset(a, 0, sizeof(a));
        dfs(0, 1);
        cout << ans << endl;
    }
    return 0;
}