[算法上] 6.递归与排列组合问题

[算法上] 6.递归与排列组合问题

目录

• ⭐递归必会题目
• • oj-240 图形打印四
  • oj-235 递归实现指数型枚举
  • oj-236 递归实现组合型枚举
  • oj-237 递归实现排列型枚举
• ⭐搜索问题
• • 深搜走地图--解决联通性问题（==深搜模板==）
  • 广搜走地图--解决联通性问题+最少步数问题
  • oj-535 瓷砖
  • oj-397 僵尸来袭
  • oj-536 最大黑色区域
  • oj-404 01迷宫简易版
  • oj-396 填涂颜色
  • 深搜版
  • 广搜版
  • oj-399 小明吃饭（==广搜模板==）
  • oj-304 骑士风度的牛
  • oj-398 马的遍历
  • oj-305 乳草的入侵

⭐递归必会题目 oj-240 图形打印四

#include
using namespace std;

//num对应图形的边长
int num[10] = {0, 1};
char mmap[3000][3000];

void init() {
    for (int i = 2; i <= 7; i++) {
        num[i] = num[i - 1] * 3;
    }
}

//画布上把n==7画出来,读入n时直接输出
//func(x, y, n)递归式子,前两个是坐标
void func(int x, int y, int n) {
    if (n == 1) {
        mmap[x][y] = 'X';
        return ;//递归出口
    }
    //左上,右上,中间,左下,右下
    func(x, y, n - 1);
    func(x, y + num[n] / 3 * 2, n - 1);
    func(x + num[n] / 3, y + num[n] / 3, n - 1);
    func(x + num[n] / 3 * 2, y, n - 1);
    func(x + num[n] / 3 * 2, y + num[n] / 3 * 2, n - 1);
}

int main() {
    init();
    func(1, 1, 7);
    int t;
    while (cin >> t) {
        if (t == -1) {
            break;
        }
        for (int i = 1; i <= num[t]; i++) {
            for (int j = 1; j <= num[t]; j++) {
                if (mmap[i][j] == 'X') {
                    cout << 'X';
                } else {
                    cout << ' ';
                }
            }
            cout << endl;
        }
        cout << '-' << endl;
    }
    return 0;
}

oj-235 递归实现指数型枚举

递归每层选一个数

n=3
①递归第一层func(1~3)
②递归第二层func(2~3)
③递归第三层func(3~3)

法1

#include 
using namespace std;

int n, num[15];

void p(int cnt) { // 打印num[1]~num[cnt]
    for (int i = 1; i <= cnt; i++) {
        if (i != 1) cout << " ";
        cout << num[i];
    }
    cout << endl;
}

void func(int s, int deep) { // s这一层从几开始选，deep这是第几层
    for (int i = s; i <= n; i++) {
        num[deep] = i;
        p(deep);
        func(i + 1, deep + 1); // 递归
    }
}

int main() {
    cin >> n;
    func(1, 1); // 从1开始选，第1层
    return 0;
}

法2：使用 cnt，递归感更强

#include 
using namespace std;

int n, num[15], cnt; // cnt层数,递归感更强

void p() {
    for (int i = 0; i <= cnt; i++) {
        i && cout << " "; // if(i) cout << " ";
        cout << num[i];
    }
    cout << endl;
}

void func(int s) {
    for (int i = s; i <= n; i++) {
        num[cnt] = i;
        p(); // 选1个数即打印
        cnt++; // 下一层
        func(i + 1); // 下一层层的数i+1开始
        cnt--; // 递归回来，原层数
    }
}

int main() {
    cin >> n;
    func(1);
    return 0;
}

oj-236 递归实现组合型枚举

#include 
using namespace std;

int n, m, num[15];

void print() {
    for (int i = 1; i <= m; i++) {
        if (i != 1) {
            cout << " ";
        }
        cout << num[i];
    }
    cout << endl;
}

//本层从s开始选,还剩left个数需要选
void func(int s, int left) {
    if (left == 0) {
        print();
        return ;
    }
    for (int i = s; i <= n; i++) {
        num[m - left + 1] = i;
        func(i + 1, left - 1);
    }
}

int main() {
    cin >> n >> m;
    func(1, m);
    return 0;
}

oj-237 递归实现排列型枚举

#include 
using namespace std;

int n, num[15], mark[15], cnt = 1;

void print() {
    for (int i = 1; i <= n; i++) {
        if (i != 1) {
            cout << " ";
        }
        cout << num[i];
    }
    cout << endl;
}

void func() {
    if (cnt == n + 1) {
        print();
        return ;
    }
    for (int i = 1; i <= n; i++) {
        if (mark[i] == 0) {
            num[cnt] = i;
            mark[i] = 1;
            cnt++;
            func();
            cnt--;
            mark[i] = 0;//解除标记
        }
    }
}

int main() {
    cin >> n;
    func();
    return 0;
}

1. 235、236、237必会题，排列组合问题，用深搜解决了问题，可以用二叉树进行模拟，使用递归：每层选一个数
2. 本质上是暴力枚举，时间复杂度O(n!)
3. c++中有一个全排列函数

⭐搜索问题

1. 搜索问题本质是暴力枚举，有2种形式：深搜（dfs）、广搜（bfs）
2. 遍历二叉树，广搜表现为层序遍历
3. 深搜用递归（栈）实现，广搜用队列实现

深搜走地图–解决联通性问题（深搜模板）

#include 
using namespace std;

int n, m, sx, sy, ex, ey;
int dir[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};//方向数组
char mmap[105][105];

//以(x, y)为起点能否走到终点
int func(int x, int y) {
    for (int i = 0; i < 4; i++) {
        int xx = x + dir[i][0];
        int yy = y + dir[i][1];
        if (xx == ex && yy == ey || mmap[xx][yy] == 'T') {
            return 1;
        }
        if (mmap[xx][yy] == '.') {
            mmap[xx][yy] = 0;
            //不写else -> return 0,因为还有其他方向
            int t = func(xx, yy);
            if (t == 1) {
                return 1;
            }
        }
    }
    return 0;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> mmap[i][j];
            if (mmap[i][j] == 'S') {
                sx = i, sy = j;
            }
            if (mmap[i][j] == 'T') {
                ex = i, ey = j;
            }
        }
    }
    int t = func(sx, sy);
    if (t == 1) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }
    return 0;
}

1. 深搜怎么走，与方向数组的定义有关，本题定义 上右下左
2. 注意地图是字符数组还是整数数组

广搜走地图–解决联通性问题+最少步数问题

均使用该套路

1. 存：状态如何存储
2. 起：起始状态
3. 终：终止状态
4. 转：状态如何转移
5. 重：如何去重

oj-535 瓷砖

#include 
using namespace std;

int n, m, sx, sy, ans = 1;//起点也算1个点
int dir[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};
char mmap[55][55];

void func(int x, int y) {
    for (int i = 0; i < 4; i++) {
        int xx = x + dir[i][0];
        int yy = y + dir[i][1];
        if (mmap[xx][yy] == '.') {
            ans++;
            mmap[xx][yy] = 0;
            func(xx, yy);
        }
    }
}

int main() {
    //常见坑:行列输入相反
    cin >> m >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> mmap[i][j];//前面不用加&
            if (mmap[i][j] == '@') {
                sx = i, sy = j;
            }
        }
    }
    func(sx, sy);//起点为'@',不用去重
    cout << ans << endl;
    return 0;
}

oj-397 僵尸来袭

连通性问题用深搜

#include
using namespace std;

int n, m, ans, mmap[105][105];
int dir[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};

void func(int x, int y) {
    for (int i = 0; i < 4; i++) {
        int xx = x + dir[i][0];
        int yy = y + dir[i][1];
        if (mmap[xx][yy] != 0) {
            mmap[xx][yy] = 0;//先置0，再递归
            func(xx, yy);
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> mmap[i][j];
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (mmap[i][j] != 0) {
                ans++;
                mmap[i][j] = 0;
                func(i, j);
            }
        }
    }
    cout << ans << endl;
    return 0;
}

oj-536 最大黑色区域

#include
using namespace std;

//temp表示每次深搜的结果
int n, m, ans, temp;
int dir[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};
char mmap[105][105];

void func(int x, int y) {
    for (int i = 0; i < 4; i++) {
        int xx = x + dir[i][0];
        int yy = y + dir[i][1];
        if (mmap[xx][yy] == '1') {
            temp++;//计数
            mmap[xx][yy] = 0;//去重
            func(xx, yy);//递归
        }
    }
}

int main() {
    cin >> n >> m;
    //每一行从下标1处开始输入,从0处输入使用cin >> mmap[i];
    for (int i = 1; i <= n; i++) {
        cin >> &mmap[i][1];//注意点
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (mmap[i][j] == '1') {
                temp = 1;
                mmap[i][j] = 0;//去重
                func(i, j);
                ans = max(ans, temp);
            }
        }
    }
    cout << ans << endl;
    return 0;
}

1. cin >> str; <==> cin >> &str[0];str 数组名是数组首地址，从mmap[i][1]开始存要取地址
2. cin >> &mmap[i][1];这种写法只适用于字符数组的输入，它可以一连串读入；不适用于整数数组，它只能一个一个读入

oj-404 01迷宫简易版

#include
using namespace std;

int n, m, ans, mark[3005][3005], sx, sy;
int dir[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};
char mmap[3005][3005];

void func(int x, int y) {
    for (int i = 0; i < 4; i++) {
        int xx = x + dir[i][0];
        int yy = y + dir[i][1];
        //判断边界,注意xx/yy边界条件不一样
        if (xx < 1 || yy < 1 || xx > n || yy > m || mark[xx][yy] == 1) {
            continue;
        }
        if (mmap[x][y] != mmap[xx][yy]) {
            ans++;
            mark[xx][yy] = 1;
            func(xx, yy);
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> &mmap[i][1];
    }
    cin >> sx >> sy;
    ans = 1;
    mark[sx][sy] = 1;
    func(sx, sy);
    cout << ans << endl;
    return 0;
}

oj-396 填涂颜色 深搜版

1. 利用补的外圈0，判断与边界联通的0，否则边界处（外层一圈）可能有多个0的起点
2. 手动判断边界

广搜版

//广搜可以解决深搜的联通性问题
//广搜还可以解决最少步数问题,因为它是按层去遍历的

#include
#include 
using namespace std;

struct node {
    int x, y;
};

int n, mmap[35][35];
int dir[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> mmap[i][j];
        }
    }
    queue que;//<>匹配类型名
    que.push((node){0, 0});
    mmap[0][0] = 3;//易忘
    while (!que.empty()) {
        node temp = que.front();
        que.pop();
        for (int i = 0; i < 4; i++) {
            int x = temp.x + dir[i][0];
            int y = temp.y + dir[i][1];
            if (x < 0 || y < 0 || x > n + 1 || y > n + 1 || mmap[x][y] == 3) {
                continue;
            }
            if (mmap[x][y] == 0) {
                mmap[x][y] = 3;
                que.push((node){x, y});
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (j != 1) {//不是第一个打印空格
                cout << " ";
            }
            if (mmap[i][j] == 3) {
                cout << 0;
            } else if (mmap[i][j] == 0) {
                cout << 2;
            } else {
                cout << 1;
            }
        }
        cout << endl;//输出一行输出换行
    }
    return 0;
}

oj-399 小明吃饭（广搜模板）

#include
#include 
using namespace std;

struct node {
    int x, y, step;
};

int n, m, sx, sy;
int dir[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};
char mmap[505][505];

int main() {
    cin >> n >> m;
    //从(1, 1)点开始读,避免判断边界
    //cin >> &mmap[i][1];要去找起点,不能这么读
    //逗号表达式,值是最后一个表达式的值
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> mmap[i][j];
            if (mmap[i][j] == '2') {
                sx = i, sy = j;
            }
        }
    }
    queue que;
    que.push((node){sx, sy});
    while (!que.empty()) {
        node temp = que.front();
        que.pop();
        for (int i = 0; i < 4; i++) {
            int x = temp.x + dir[i][0];
            int y = temp.y + dir[i][1];
            //if (x < 1 ... )从(1,1)开始读避免判断边界
            if (mmap[x][y] == '3') {
                cout << temp.step + 1 << endl;
                return 0;
            }
            if (mmap[x][y] == '.') {
                mmap[x][y] = 0;
                que.push((node){x, y, temp.step + 1});
            }
        }
    }
    cout << -1 << endl;
    return 0;
}

oj-304 骑士风度的牛

#include
#include 
using namespace std;

struct node {
    int x, y, step;
};

int n, m;
int dir[8][2] = {1, 2, 2, 1, 2, -1, 1, -2, -1, -2, -2, -1, -1, 2, -2, 1};
char mmap[200][200];

int main() {
    cin >> m >> n;//先输入列数再输入行数
    queue que;//先定义队列,输入时判断起点直接入队
    for (int i = 5; i <= n + 4; i++) {//日字形走位,防止出界,起码从(2,2)点读入,i/j的边界条件
        for (int j = 5; j <= m + 4; j++) {
            cin >> mmap[i][j];
            if (mmap[i][j] == 'K') {//起点
                que.push((node){i, j, 0});
            }
        }
    }
    while (!que.empty()) {
        node temp = que.front();
        que.pop();
        for (int i = 0; i < 8; i++) {
            int x = temp.x + dir[i][0];
            int y = temp.y + dir[i][1];
            if (mmap[x][y] == 'H') {
                cout << temp.step + 1 << endl;//输出原步数+1
                return 0;
            }
            if (mmap[x][y] == '.') {
                mmap[x][y] = 0;//去重,只要不是'.'和'T'
                que.push((node){x, y, temp.step + 1});//入队时原步数+1
            }
        }
    }
    cout << -1 << endl;
    return 0;
}

oj-398 马的遍历

#include
#include 
#include //memset头文件
using namespace std;

struct node {
    int x, y, step;
};

//num是地图,同时起去重作用
//dir的8个方向有规律:1,2,-1,-2的排列
int num[405][405], n, m, sx, sy;
int dir[8][2] = {1, 2, 1, -2, -1, 2, -1, -2, 2, 1, 2, -1, -2, 1, -2, -1};

int main() {
    memset(num, -1, sizeof(num));//初始化为-1最方便,初始化为0要判断是否是起点
    cin >> n >> m >> sx >> sy;
    num[sx][sy] = 0;//num标记为0
    queue que;
    que.push((node){sx, sy, 0});
    while (!que.empty()) {
        node temp = que.front();
        que.pop();
        for (int i = 0; i < 8; i++) {
            int x = temp.x + dir[i][0];
            int y = temp.y + dir[i][1];
            //从(1,1)开始存,要判断边界及标记过的情况
            if (x < 1 || y < 1 || x > n || y > m || num[x][y] != -1) {
                continue;
            }
            if (num[x][y] == -1) {
                num[x][y] = temp.step + 1;
                que.push((node){x, y, num[x][y]});
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (j != 1) {
                cout << " ";
            }
            cout << num[i][j];
        }
        cout << endl;
    }
    return 0;
}

oj-305 乳草的入侵

#include
#include 
using namespace std;

struct node {
    int x, y, step;
};

int n, m, sx, sy;
int dir[8][2] = {0, 1, 1, 0, 0, -1, -1, 0, 1, 1, 1, -1, -1, 1, -1, -1};
char mmap[105][105];

int main() {
    //先读列,再读行,,先读列坐标,再读行坐标
    cin >> m >> n >> sy >> sx;
    sx = n - sx + 1;//行坐标转换(1,1)->(n,1)
    for (int i = 1; i <= n; i++) {
        cin >> &mmap[i][1];
    }
    int ans = 0;
    queue que;
    que.push((node){sx, sy, 0});
    mmap[sx][sy] = 0;//标记掉起点,去重
    while (!que.empty()) {
        node temp = que.front();
        ans = temp.step;//没有边界判断,最后一个出队的一定是最远的
        que.pop();
        for (int i = 0; i < 8; i++) {
            int x = temp.x + dir[i][0];
            int y = temp.y + dir[i][1];
            //没有边界判断
            if (mmap[x][y] == '.') {
                mmap[x][y] = 0;//去重
                que.push((node){x, y, temp.step + 1});
            }
        }
    }
    cout << ans << endl;
    return 0;
}