蓝桥打卡-Day13

1.带分数（全排列） https://www.lanqiao.cn/problems/208/learning/

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
long n;           // 这是目标
int cnt;          // 计数器
bool number[10];  // 1-9 代表九位数字,flase 表示没用过，true 表示用过了
int state[10];      // 表示10位数字
long a, b, c, tmp;  // n=100 * c == a * c + b
void dfs(int u) {
    // 如果大于9，就代表穷举数字结束了，9 个位置都有数字s了
    if (u > 9) {
        /* dfs 测试语句
        for (int i = 1; i <= 9; i++) printf("%d", state[i]);
        puts("");
        */
        //那现在就是把这数字分割开来，分成 a, b,c 三部分
        // 先砍一刀在ab之间，目的是把 a 分出来
        for (int ab = 1; ab <= 9; ab++) {
            //再砍一刀，把 b 分出来
            for (int bc = ab + 1; bc <= 9; bc++) {
                int a = 0, b = 0, c = 0;
                tmp = ab;
                for (tmp; tmp != 0; tmp--) {
                    a = a * 10 + state[tmp];
                    if (a >= n) break;  // 剪枝
                }
                // cout << "a=" << a << endl;
                tmp = bc;
                for (tmp; tmp != ab; tmp--) {
                    b = b * 10 + state[tmp];
                }
                // cout << "b=" << b << endl;
                tmp = 9;
                for (tmp; tmp != bc; tmp--) {
                    c = c * 10 + state[tmp];
                }
                // cout << "c=" << c << endl;

                // cout << a << " " << b << " " << c << endl;
                //    都选择完了，那就看看是不是符合条件喽
                if (n * c == a * c + b) {
                    cnt++;
                    return;
                }
            }
        }
    }
    // 否则没结束，还有位数是空的
    // 先把 u 这一位的数字给确定了
    for (int i = 1; i <= 9; i++) {
        if (!number[i]) {
            // 如果没用过，就往下递推
            number[i] = true;
            state[u] = i;
            dfs(u + 1);
            number[i] = false;
        }
    }
}
int main() {
    scanf("%ld", &n);
    //这个意思表示第一位，123456789，总共九位
    dfs(1);
    printf("%d", cnt);
    return 0;
}

2.走迷宫（bfs）https://www.lanqiao.cn/problems/1216/learning/

#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
#define x first
#define y second
using namespace std;

typedef pair<int, int> PII;
const int N = 110;
int n, m;

int map[N][N];
int idx[N][N];

int dx[4] = {0, -1, 0, 1}, dy[4] = {-1, 0, 1, 0};

void bfs(int x1, int y1, int x2, int y2) {
    memset(idx, -1, sizeof idx);
    queue<PII> q;
    q.push({x1, y1});
    idx[x1][y1] = 0;
    while (!q.empty()) {
        auto t = q.front();
        for (int i = 0; i < 4; i++) {
            int x = t.x + dx[i], y = t.y + dy[i];
            if (x < 1 && y < 1 && x > m && y > n) continue;
            if (map[x][y] == 0) continue;
            if (idx[x][y] != -1) continue;
            idx[x][y] = idx[t.x][t.y] + 1;
            q.push({x, y});
            if (x == x2 && y == y2) return;
        }
        q.pop();
    }
    return;
}

int main() {
    scanf("%d%d", &n, &m);

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) scanf("%d", &map[i][j]);

    int x1, y1, x2, y2;

    scanf("%d%d%d%d", &x1, &y1, &x2, &y2);

    bfs(x1, y1, x2, y2);

    if (idx[x2][y2] != -1)
        printf("%d\n", idx[x2][y2]);
    else
        printf("-1\n");

    return 0;
}

3.蓝桥幼儿园（并查集）https://www.lanqiao.cn/problems/1135/learning/
4.跳石头（贪心+二分）https://www.lanqiao.cn/problems/364/learning/