7 递归/搜索参考代码

RonChen / 2023-08-07 / 原文

P5739 [深基7.例7] 计算阶乘

#include <cstdio>
int factor(int x) {
    if (x == 0) return 1;
    return x * factor(x - 1);
}
int main()
{
    int n;
    scanf("%d", &n);
    printf("%d\n", factor(n));
    return 0;
}

P1028 [NOIP2001 普及组] 数的计算

#include <cstdio>
const int MAXN = 1005;
int f[MAXN];
int solve(int n) {
    int ret = 1;
    if (f[n] != -1) return f[n];
    for (int i = 1; i <= n / 2; i++) ret += solve(i);
    return f[n] = ret;
}
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) f[i] = -1;
    printf("%d\n", solve(n));
    return 0;
}

P1464 Function

#include <cstdio>
typedef long long LL;
bool vis[25][25][25];
LL mem[25][25][25];
int f(LL a, LL b, LL c) {
    if (a <= 0 || b <= 0 || c <= 0) return 1;
    if (a > 20 || b > 20 || c > 20) return f(20, 20, 20);
    if (vis[a][b][c]) return mem[a][b][c];
    if (a < b && b < c) {
        int ret = f(a, b, c - 1) + f(a, b - 1, c - 1) - f(a, b - 1, c);
        vis[a][b][c] = true;
        return mem[a][b][c] = ret;
    }
    int ret = f(a - 1, b, c) + f(a - 1, b - 1, c) + f(a - 1, b, c - 1) - f(a - 1, b - 1, c - 1);
    vis[a][b][c] = true;
    return mem[a][b][c] = ret;
}
int main()
{
    while (true) {
        LL a, b, c;
        scanf("%lld%lld%lld", &a, &b, &c);
        if (a == -1 && b == -1 && c == -1) break;
        printf("w(%lld, %lld, %lld) = %d\n", a, b, c, f(a, b, c));
    }
    return 0;
}

P1010 [NOIP1998 普及组] 幂次方

#include <bits/stdc++.h>
using namespace std;
string divide(int x) {
    if (x == 0) return "0";
    if (x == 1) return "2(0)";
    if (x == 2) return "2";
    vector<int> vec;
    int cur = 0;
    while (x > 0) {
        if (x % 2 != 0) vec.push_back(cur);
        x /= 2;
        ++cur;
    }
    string ret;
    int len = vec.size();
    for (int i = len - 1; i >= 0; i--) {
        if (i != len - 1) ret += "+";
        ret += "2";
        if (vec[i] != 1) {
            ret += "("; ret += divide(vec[i]); ret += ")";
        }
    }
    return ret;
}
int main()
{
    int n;
    cin >> n;
    cout << divide(n) << endl;
    return 0;
}

P2404 自然数的拆分问题

#include<cstdio>
int n, a[10];
void dfs(int r, int p, int idx) {
	if (r==0) {
		if (idx > 1) {
			for (int i = 0; i < idx; i++) {
				if (i>0) printf("+");
				printf("%d", a[i]);
			}
			printf("\n");
		}
		return;
	}
	for (int i = p; i <= r; i++) {
		a[idx]=i;
		dfs(r - i, i, idx + 1);
	}
}
int main() {
	scanf("%d", &n);
	dfs(n, 1, 0);
	return 0;
}

P1706 全排列问题

#include <cstdio>
const int MAXN = 10;
int ans[MAXN], n;
bool used[MAXN];
void dfs(int cur) {
    if (cur > n) {
        for (int i = 1; i <= n; i++) printf("%5d", ans[i]);
        printf("\n");
        return;
    }
    for (int i = 1; i <= n; i++) 
        if (!used[i]) {
            used[i] = true;
            ans[cur] = i;
            dfs(cur + 1);
            used[i] = false;
        }
}
int main()
{
    scanf("%d", &n);
    dfs(1);
    return 0;
}

P1036 [NOIP2002 普及组] 选数

#include <cstdio>
const int MAXN = 25;
int x[MAXN], n, k, ans;
bool isprime(int num) {
    if (num < 2) return false;
    for (int i = 2; i * i <= num; i++)
        if (num % i == 0) return false;
    return true;
}
void dfs(int cur, int sum, int cnt) {
    if (cnt == k) {
        if (isprime(sum)) ans++;
        return;
    }
    if (cur > n) return;
    dfs(cur + 1, sum, cnt);
    dfs(cur + 1, sum + x[cur], cnt + 1);
}
int main()
{
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) scanf("%d", &x[i]);
    dfs(1, 0, 0);
    printf("%d\n", ans);
    return 0;
}

P1605 迷宫

#include <cstdio>
int n, m, t, ans;
int sx, sy, fx, fy;
int b[10][10];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
void dfs(int x, int y) {
    if (x == fx && y == fy) {
        ++ans;
        return;
    }
    for (int i = 0; i < 4; ++i) {
        int xx = x + dx[i];
        int yy = y + dy[i];
        if (xx >= 1 && xx <= n && yy >= 1 && yy <= m && b[xx][yy] == 0) {
            b[xx][yy] = 1; // (xx,yy)被走过
            dfs(xx, yy);
            b[xx][yy] = 0; // 复原
        }
    }
}
int main()
{
    scanf("%d%d%d%d%d%d%d", &n, &m, &t, &sx, &sy, &fx, &fy);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j) 
            b[i][j] = 0;
    for (int i = 0; i < t; ++i) {
        int x, y;
        scanf("%d%d", &x, &y);
        b[x][y] = 2;
    }
    b[sx][sy] = 1;
    dfs(sx, sy);
    printf("%d\n", ans);
    return 0;
}

P1644 跳马问题

#include <cstdio>
const int MAXN = 20;
int n, m, ans;
int dx[4] = {-2, -1, 1, 2};
int dy[4] = {1, 2, 2, 1};
void dfs(int x, int y) {
    if (x == n && y == m) {
        ans++;
        return;
    }
    for (int i = 0; i < 4; i++) {
        int xx = x + dx[i], yy = y + dy[i];
        if (xx >= 0 && xx <= n && yy <= m) dfs(xx, yy);
    }
}
int main()
{
    scanf("%d%d", &n, &m);
    dfs(0, 0);
    printf("%d\n", ans);
    return 0;
}

P1596 [USACO10OCT] Lake Counting S

DFS

#include <cstdio>
char f[105][105];
int n, m;
int dx[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dy[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
void dfs(int x, int y) {
    f[x][y] = '.';
    for (int i = 0; i < 8; i++) {
        int xx = x + dx[i];
        int yy = y + dy[i];
        if (xx >= 0 && xx < n && yy >= 0 && yy < m && f[xx][yy] == 'W') {
            dfs(xx, yy);
        }
    }
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) scanf("%s", f[i]);
    int lake = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) 
            if (f[i][j] == 'W') {
                lake++;
                dfs(i, j);
            }
    printf("%d\n", lake);
    return 0;
}

BFS

#include <cstdio>
#include <queue>
using namespace std;
char f[105][105];
int n, m;
int dx[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dy[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
struct Node {
    int x, y;
};
void bfs(int x, int y) {
    f[x][y] = '.';
    queue<Node> q;
    q.push({x, y});
    while (!q.empty()) {
        Node t = q.front(); q.pop();
        for (int i = 0; i < 8; i++) {
            int xx = t.x + dx[i], yy = t.y + dy[i];
            if (xx >= 0 && xx < n && yy >= 0 && yy < m && f[xx][yy] == 'W') {
                f[xx][yy] = '.';
                q.push({xx, yy});
            }
        }
    }
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) scanf("%s", f[i]);
    int lake = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) 
            if (f[i][j] == 'W') {
                lake++;
                bfs(i, j);
            }
    printf("%d\n", lake);
    return 0;
}

P1162 填涂颜色

#include <cstdio>
int n, a[35][35];
int dx[4] = {-1, 0, 0, 1};
int dy[4] = {0, -1, 1, 0};
void dfs(int x, int y, int p) {
    a[x][y] = p;
    for (int i = 0; i < 4; ++i) {
        int xx = x + dx[i];
        int yy = y + dy[i];
        if (xx >= 0 && xx < n && yy >= 0 && yy < n && a[xx][yy] == 0) {
            dfs(xx, yy, p);
        }
    }
}
int main() 
{
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j) 
            scanf("%d", &a[i][j]);
    for (int i = 0; i < n; ++i) {
        if (a[0][i] == 0) dfs(0, i, -1);
        if (a[n - 1][i] == 0) dfs(n - 1, i, -1);
        if (a[i][0] == 0) dfs(i, 0, -1);
        if (a[i][n - 1] == 0) dfs(i, n - 1, -1);
    }
    for (int i = 1; i < n - 1; ++i)
        for (int j = 1; j < n - 1; ++j)
            if (a[i][j] == 0) dfs(i, j, 2);
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            printf("%d%s", a[i][j] == -1 ? 0 : a[i][j], j + 1 == n ? "\n" : " ");
    return 0;
}

P1588 [USACO07OPEN] Catch That Cow S

#include <cstdio>
#include <queue>
using namespace std;
const int MAXN = 100005;
int ans[MAXN];
int main()
{
    int t;
    scanf("%d", &t);
    while (t--) {
        for (int i = 0; i < MAXN; i++) ans[i] = -1;
        int x, y;
        scanf("%d%d", &x, &y);
        queue<int> q;
        q.push(x); ans[x] = 0;
        while (!q.empty()) {
            int cur = q.front(); q.pop();
            if (cur == y) break;
            if (cur + 1 < MAXN && ans[cur + 1] == -1) {
                ans[cur + 1] = ans[cur] + 1; q.push(cur + 1); // 前进一步
            }
            if (cur - 1 > 0 && ans[cur - 1] == -1) {
                ans[cur - 1] = ans[cur] + 1; q.push(cur - 1); // 后退一步
            }
            if (cur * 2 < MAXN && ans[cur * 2] == -1) {
                ans[cur * 2] = ans[cur] + 1; q.push(cur * 2); // 走到2倍位置
            }
        }
        printf("%d\n", ans[y]);
    }
    return 0;
}

P5461 赦免战俘

#include <cstdio>
int a[1100][1100];
int n;
void print() {
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            printf("%d%s", a[i][j], j + 1 == n ? "\n" : " ");
}
void solve(int x, int y, int n) {
    if (n == 0) return;
    for (int i = x; i < x + n / 2; ++i)
        for (int j = y; j < y + n / 2; ++j)
            a[i][j] = 0;
    solve(x + n / 2, y, n / 2);
    solve(x, y + n / 2, n / 2);
    solve(x + n / 2, y + n / 2, n / 2);
}
int main()
{
    scanf("%d", &n);
    n = 1 << n;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            a[i][j] = 1;
    solve(0, 0, n);
    print();
    return 0;
}

P1928 外星密码

#include <iostream>
#include <string>
using namespace std;
string s;
int len, idx;
string solve() {
    string ret, tmp;
    int rep = 0;
    while (idx < len && s[idx] != ']') {
        if (s[idx] == '[') {
            ++idx;
            tmp += solve();
        } else if (s[idx] >= '0' && s[idx] <= '9') {
            rep = rep * 10 + s[idx] - 48;
            ++idx;
        } else {
            tmp += s[idx];
            ++idx;
        }
    }
    ++idx;
    ret += tmp;
    for (int i = 0; i < rep - 1; ++i) ret += tmp;
    return ret;
}
int main()
{
    cin >> s;
    len = s.size();
    cout << solve() << endl;
    return 0;
}

P1228 地毯填补问题

#include <cstdio>
int px, py;
int judge(int xx, int yy, int x, int y, int n) {
    if (xx < x + n / 2) return yy < y + n / 2 ? 1 : 2;
    return yy < y + n / 2 ? 3 : 4;
}
void dfs(int n, int x, int y, int miss, int xx, int yy) {
    if (n == 1) return;
    n = n / 2;
    if (miss == 1) {
        printf("%d %d %d\n", x + n, y + n, 1);
        dfs(n, x, y, judge(xx, yy, x, y, n), xx, yy);
        dfs(n, x, y + n, 3, x + n - 1, y + n);
        dfs(n, x + n, y, 2, x + n, y + n - 1);
        dfs(n, x + n, y + n, 1, x + n, y + n);
    } else if (miss == 2) {
        printf("%d %d %d\n", x + n, y + n - 1, 2);
        dfs(n, x, y, 4, x + n - 1, y + n - 1);
        dfs(n, x, y + n, judge(xx, yy, x, y + n, n), xx, yy);
        dfs(n, x + n, y, 2, x + n, y + n - 1);
        dfs(n, x + n, y + n, 1, x + n, y + n);
    } else if (miss == 3) {
        printf("%d %d %d\n", x + n - 1, y + n, 3);
        dfs(n, x, y, 4, x + n - 1, y + n - 1);
        dfs(n, x, y + n, 3, x + n - 1, y + n);
        dfs(n, x + n, y, judge(xx, yy, x + n, y, n), xx, yy);
        dfs(n, x + n, y + n, 1, x + n, y + n);
    } else { 
        printf("%d %d %d\n", x + n - 1, y + n - 1, 4);
        dfs(n, x, y, 4, x + n - 1, y + n - 1);
        dfs(n, x, y + n, 3, x + n - 1, y + n);
        dfs(n, x + n, y, 2, x + n, y + n - 1);
        dfs(n, x + n, y + n, judge(xx, yy, x + n, y + n, n), xx, yy);
    }
}
int main()
{
    int k;
    scanf("%d%d%d", &k, &px, &py);
    int n = 1 << k;
    dfs(n, 1, 1, judge(px, py, 1, 1, n), px, py);
    return 0;
}

P1219 [USACO1.5] 八皇后 Checker Challenge

#include <cstdio>
const int MAXN = 30;
int n, cnt;
int ans[MAXN], c[MAXN], d1[MAXN], d2[MAXN];
void dfs(int i) {
    if (i > n) {
        cnt++;
        if (cnt <= 3) {
            for (int j = 1; j <= n; j++) printf("%d ", ans[j]);
            printf("\n");
        }
        return;
    }
    for (int j = 1; j <= n; j++) {
        if (!c[j] && !d1[i + j] && !d2[i - j + n]) {
            ans[i] = j; // 记录第i行的皇后放在了第j列
            c[j] = d1[i + j] = d2[i - j + n] = 1; // 标记
            dfs(i + 1);
            c[j] = d1[i + j] = d2[i - j + n] = 0; // 复原
        }
    }
}
int main()
{
    scanf("%d", &n);
    dfs(1);
    printf("%d\n", cnt);
    return 0;
}

P1443 马的遍历

#include <cstdio>
#include <queue>
using namespace std;
struct Status {
    int x, y, step;
};
int ans[405][405];
int dx[8] = {-1, -2, -2, -1, 1, 2, 2, 1};
int dy[8] = {-2, -1, 1, 2, -2, -1, 1, 2};
int main()
{
    int n, m, x, y;
    scanf("%d%d%d%d", &n, &m, &x, &y);
    --x; --y;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j) {
            ans[i][j] = -1;
        }
    int step = 0;   
    queue<Status> que;
    que.push({x, y, 0});
    ans[x][y] = 0;
    while (!que.empty()) {
        Status t = que.front();
        que.pop();
        for (int i = 0; i < 8; ++i) {
            int xx = t.x + dx[i];
            int yy = t.y + dy[i];
            if (xx >= 0 && xx < n && yy >= 0 && yy < m && ans[xx][yy] == -1) {
                ans[xx][yy] = t.step + 1;
                que.push({xx, yy, ans[xx][yy]});
            }
        }
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) printf("%-5d", ans[i][j]);
        printf("\n");
    }
    return 0;
}

P1135 奇怪的电梯

#include <cstdio>
#include <queue>
using namespace std;
struct Status {
    int cur, step;
}; 
int vis[205], k[205];
int main()
{
    int n, a, b;
    scanf("%d%d%d", &n, &a, &b);
    for (int i = 1; i <= n; ++i) scanf("%d", &k[i]);
    queue<Status> que;
    que.push({a, 0});
    vis[a] = 1;
    while (!que.empty()) {
        Status t = que.front();
        if (t.cur == b) {
            printf("%d\n", t.step);
            return 0;
        }
        que.pop();
        int up = t.cur + k[t.cur];
        if (up <= n && !vis[up]) {
            que.push({up, t.step + 1});
            vis[up] = 1; 
        }
        int down = t.cur - k[t.cur];
        if (down > 0 && !vis[down]) {
            que.push({down, t.step + 1});
            vis[down] = 1; 
        }
    }
    printf("-1\n");
    return 0;
}

P2895 [USACO08FEB] Meteor Shower S

#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;
const int MAXN = 305;
struct Status {
    int x, y, step;
};
int m, a[MAXN][MAXN];
int dx[4] = {-1, 0, 0, 1};
int dy[4] = {0, -1, 1, 0};
bool vis[MAXN][MAXN];
int main()
{
    scanf("%d", &m);
    for (int i = 0; i < MAXN; ++i)
        for (int j = 0; j < MAXN; ++j)
            a[i][j] = 10000;
    for (int i = 0; i < m; ++i) {
        int x, y, t;
        scanf("%d%d%d", &x, &y, &t);
        a[x][y] = min(a[x][y], t);
        for (int j = 0; j < 4; ++j) {
            int xx = x + dx[j];
            int yy = y + dy[j];
            if (xx >= 0 && xx < MAXN && yy >= 0 && yy < MAXN && t < a[xx][yy]) {
                a[xx][yy] = t;
            }
        }
    }
    queue<Status> que;
    que.push({0, 0, 0});
    vis[0][0] = true;
    while (!que.empty()) {
        Status cur = que.front();
        que.pop();
        if (a[cur.x][cur.y] == 10000) {
            printf("%d\n", cur.step);
            return 0;
        }
        for (int i = 0; i < 4; ++i) {
            int x = cur.x + dx[i];
            int y = cur.y + dy[i];
            int step = cur.step + 1;
            if (x >= 0 && y >= 0 && x < MAXN && y < MAXN && step < a[x][y] && !vis[x][y]) {
                vis[x][y] = true;
                que.push({x, y, step});
            }
        }
    }
    printf("-1\n");
    return 0;
}

P1825 [USACO11OPEN] Corn Maze S

#include <cstdio>
#include <queue>
#include <utility>
using namespace std;
const int MAXN = 305;
int n, m;
int dx[4] = {-1, 0, 0, 1};
int dy[4] = {0, -1, 1, 0};
char a[MAXN][MAXN];
bool vis[MAXN][MAXN];
vector<pair<int, int>> tr[30];
struct Status {
    int x, y, step;
}; 
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; ++i) scanf("%s", a[i]);
    int x = -1, y = -1, tx = -1, ty = -1;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (a[i][j] >= 'A' && a[i][j] <= 'Z') {
                int o = a[i][j] - 'A';
                tr[o].push_back({i, j});
            }
            if (a[i][j] == '@') {
                x = i;
                y = j;
            }
            if (a[i][j] == '=') {
                tx = i; 
                ty = j;
            }
        }
    }
    queue<Status> que;
    que.push({x, y, 0});
    vis[x][y] = true;
    while (!que.empty()) {
        Status cur = que.front();
        que.pop();
        if (cur.x == tx && cur.y == ty) {
            printf("%d\n", cur.step);
            return 0;
        }
        for (int i = 0; i < 4; ++i) {
            int xx = cur.x + dx[i];
            int yy = cur.y + dy[i];
            if (xx >= 0 && xx < n && yy >= 0 && yy < m && a[xx][yy] != '#' && !vis[xx][yy]) {
                vis[xx][yy] = true;
                if (a[xx][yy] >= 'A' && a[xx][yy] <= 'Z') {
                    int o = a[xx][yy] - 'A';
                    if (tr[o][0].first == xx && tr[o][0].second == yy) {
                        xx = tr[o][1].first;
                        yy = tr[o][1].second;
                    } else {
                        xx = tr[o][0].first;
                        yy = tr[o][0].second;
                    }
                }
                que.push({xx, yy, cur.step + 1});
            }
        }
    }
    return 0;
}

P2960 [USACO09OCT] Invasion of the Milkweed G

#include <cstdio>
#include <queue>
using namespace std;
const int MAXN = 105;
char land[MAXN][MAXN];
int dx[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dy[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
struct Node {
    int x, y, step;
};
int main()
{
    int x, y, mx, my;
    scanf("%d%d%d%d", &x, &y, &mx, &my);
    for (int i = 0; i < y; i++) scanf("%s", land[i]);
    int rest = x * y;
    for (int i = 0; i < y; i++)
        for (int j = 0; j < x; j++)
            if (land[i][j] == '*') rest--;
    int sx = y - my, sy = mx - 1;
    rest--; land[sx][sy] = 'M';
    queue<Node> q;
    q.push({sx, sy, 0});
    int ans = 0;
    while (!q.empty()) {
        Node cur = q.front(); q.pop();
        for (int i = 0; i < 8; i++) {
            int xx = cur.x + dx[i], yy = cur.y + dy[i];
            if (xx >= 0 && xx < y && yy >= 0 && yy < x && land[xx][yy] == '.') {
                land[xx][yy] = 'M'; rest--;
                if (rest == 0) ans = cur.step + 1;
                q.push({xx, yy, cur.step + 1});
            } 
        }
    }
    printf("%d\n", ans);
    return 0;
}