迷宫

#include <bits/stdc++.h>
using namespace std;
int n, m, t, sx, sy, fx, fy, ans;
int a[10][10]; //-1表示障碍，0表示允许走
int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};
bool used[10][10]; //每个点有没有走过
void dfs(int x, int y)
{
    if (x == fx && y == fy)
    {
        ans++;
        return;
    }
    for (int i = 0; i < 4; i++)
    {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (a[nx][ny] == 0 && used[nx][ny] == false)
        {
            used[nx][ny] = true;
            dfs(nx, ny);
            used[nx][ny] = false;
        }
    }
}
int main()
{
    cin >> n >> m >> t;
    memset(a, -1, sizeof(a));
    memset(used, false, sizeof(used));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            a[i][j] = 0;
    cin >> sx >> sy >> fx >> fy;
    for (int i = 1; i <= t; i++)
    {
        int x, y;
        cin >> x >> y;
        a[x][y] = -1;
    }
    //走迷宫
    ans = 0;
    used[sx][sy] = true;
    dfs(sx, sy);
    cout << ans << endl;
    return 0;
}

选数

#include <bits/stdc++.h>
using namespace std;
int ans;
int n, k;
int a[30];
bool p(int n)
{
    if (n == 2 || n == 3)
        return true;
    if (n % 6 != 1 && n % 6 != 5)
        return false;
    for (int i = 5; i * i <= n; i += 6)
        if (n % i == 0 || n % (i + 2) == 0)
            return false;
    return true;
}
int choose, now;
void dfs(int step)
{
    if (choose == k && p(now))
        ans++;
    if (step == n || choose == k)
        return;
    //选当前的数
    choose++;
    now += a[step];
    dfs(step + 1);
    choose--;
    now -= a[step];
    //不选当前的数
    dfs(step + 1);
}
int main()
{
    cin >> n >> k;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    choose = 0;
    now = 0;
    dfs(0);
    cout << ans << endl;
    return 0;
}

perket

#include <bits/stdc++.h>
using namespace std;
int n;
int a[11], b[11];
int ans = 2000000000;
void dfs(int dep, int suan, int tian, bool flag)
{
    if (flag)
    {
        ans = min(abs(suan - tian), ans);
    }
    if (dep > n)
    {
        return;
    }
    dfs(dep + 1, suan * a[dep], tian + b[dep], true);
    dfs(dep + 1, suan, tian, flag);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i] >> b[i];
    }
    dfs(1, 1, 0, false);
    cout << ans << endl;
    return 0;
}

方格填数

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n, nn, sum;
int ans[5][5], rowsum[5], colsum[5], a[20];
bool vis[20];
void dfs(int x, int y)
{
    if (x < n && y > n)
    {
        x++;
        y = 1;
    }
    if (y == 1 && x > 1)
        if (rowsum[x - 1] != sum)
            return;
    if (x == n && y > 1)
        if (colsum[y - 1] != sum)
            return;
    if (x == n && y == n + 1)
    {
        int ts = 0;
        for (int i = 1; i <= n; i++)
            ts += ans[i][i];
        if (ts != sum)
            return;
        ts = 0;
        for (int i = 1; i <= n; i++)
            ts += ans[i][n-i+1];
        if (ts != sum)
            return;
        cout << sum << endl;
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= n; j++)
                cout << ans[i][j] << " ";
            cout << endl;
        }
        exit(0);
    }
    for (int i = 1; i <= nn; i++)
    {
        if (!vis[i])
        {
            ans[x][y] = a[i];
            vis[i] = true;
            rowsum[x] += a[i];
            colsum[y] += a[i];
            dfs(x, y + 1);
            vis[i] = false;
            rowsum[x] -= a[i];
            colsum[y] -= a[i];
        }
    }
}
int main()
{
    cin >> n;
    nn = n * n;
    sum = 0;
    for (int i = 1; i <= nn; i++)
    {
        cin >> a[i];
        sum += a[i];
    }
    sum /= n;
    sort(a + 1, a + nn + 1);
    memset(vis, false, sizeof(vis));
    memset(rowsum, 0, sizeof(rowsum));
    memset(colsum, 0, sizeof(colsum));
    dfs(1, 1);
    return 0;
}

取数游戏

#include <bits/stdc++.h>
using namespace std;
int T, n, m, ans;
int a[10][16];
bool used[10][16];
void dfs(int x, int y, int now)
{
    if (x > n)
    {
        ans = max(ans, now);
        return;
    }
    bool flag = true;
    for (int i = -1; i <= 1; i++)
        for (int j = -1; j <= 1; j++)
            if (used[x + i][y + j])
            {
                flag = false;
                break;
            }
    int nx = x;
    int ny = y + 1;
    if (ny > m)
        nx++, ny = 1;
    if (flag)
    {
        //取这个数
        used[x][y] = true;
        dfs(nx, ny, now + a[x][y]);
        used[x][y] = false;
        //不取这个数
        dfs(nx, ny, now);
    }
    else
        dfs(nx, ny, now);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> T;
    while (T--)
    {
        cin >> n >> m;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                cin >> a[i][j];
        ans = 0;
        memset(used, false, sizeof(used));
        dfs(1, 1, 0);
        cout << ans << "\n";
    }
    return 0;
}