逃离迷宫

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 110;

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

char g[N][N];
bool st[N][N];
int n, m;
int k, X1, Y1, X2, Y2;
bool flag;

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

bool bfs() {
    queue<node> q;
    node One, next;
    One.x = X1, One.y = Y1, One.s = -1;
    q.push(One);
    st[X1][Y1] = true;

    while (q.size()) {
        auto t = q.front();
        q.pop();

        if (t.x == X2 && t.y == Y2 && t.s <= k)
            return true;

        for (int i = 0; i < 4; i ++ ) {

            next.x = t.x + dx[i], next.y = t.y + dy[i];
            next.s = t.s + 1;

            while (next.x >= 1 && next.x <= m && next.y >= 1 && next.y <= n && g[next.x][next.y] == '.') {
                if (!st[next.x][next.y]) {
                    st[next.x][next.y] = true;
                    q.push(next);
                }

                next.x = next.x + dx[i], next.y = next.y + dy[i];
            }
        }
    }

    return false;
}

int main() {
    int t;
    cin >> t;

    while (t -- ) {
        flag = false;
        memset(st, false, sizeof st);

        cin >> m >> n;

        for (int i = 1; i <= m; i ++ )

            scanf("%s", g[i] + 1);
        cin >> k >> Y1 >> X1 >> Y2 >> X2;

        flag = bfs();

        if (!flag)
            puts("no");
        else
            puts("yes");
    }

    return 0;
}

蜘蛛牌

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

#define INF 0x3f3f3f3f

const int N = 20;

int a[N];  // a[i]表示花色是i的牌的编号是a[i]
bool st[N]; // st[i] 表示花色是i的牌已经确定了位置
int ans;

void dfs(int v, int s) { // v:深搜的次数(已经确定好位置的牌的数量) s:当前搜索的距离
    if (s >= ans )
        return;

    if (v == 9) {
        if (s < ans)
            ans = s;
        return;
    }

    for (int i = 1; i <= 9; i ++ ) {

        if (!st[i]) {
            for (int j = i + 1; j <= 10; j ++ ) {

                if (!st[j]) {
                    st[i] = true;
                    dfs(v + 1, s + abs(a[j] - a[i]));
                    break;
                }
            }

            st[i] = false;
        }
    }
}

int main() {
    int t;
    cin >> t;

    while (t -- ) {
        memset(st, false, sizeof st);
        ans = INF;

        for (int i = 1; i <= 10; i ++ ) {

            int x;
            cin >> x;
            a[x] = i;
        }

        dfs(0, 0);

        cout << ans << endl;
    }

    return 0;
}

迷宫城堡

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;

const int M = 1000010;

int h[N], e[M], ne[M], idx;
int n, m;
bool flag, Flag;
int cnt;
bool st[N];

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void dfs(int v) {
    if (cnt == n - 1) {
        Flag = true;
        return;
    }

    for (int i = h[v]; i != -1; i = ne[i]) {

        int t = e[i];

        if (!st[t]) {
            st[t] = true;
            cnt ++ ;
            dfs(t);

            if (Flag)
                return;
        }
    }
}

int main() {
    while (cin >> n >> m) {
        if (n == 0 && m == 0)
            break;

        idx = 0;
        memset(h, -1, sizeof h);

        while (m -- ) {
            int a, b;
            cin >> a >> b;
            add(a, b);
        }

        flag = true;

        for (int i = 1; i <= n; i ++ ) {

            cnt = 0;
            Flag = false;
            memset(st, false, sizeof st);
            st[i] = true;
            dfs(i);

            if (cnt < n - 1) {
                flag = false;
                break;
            }
        }

        if (!flag)
            puts("No");
        else
            puts("Yes");
    }

    return 0;
}

Sticks

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 70;

int n, a[N];
bool flag, st[N];
int MAX;

bool cmp(int a, int b) {
    return a > b;
}


void dfs(int res, int v) {
    // 找到答案，返回
    if (flag)
        return;

    // 如果所有都被选择 flag置true，表示找到
    if (v == n) {
        flag = true;
        return;
    }

    // 如果res = 0 且并非所有都被选择，则继续将MAX dfs
    if (res == 0 && v < n)
        dfs(MAX, v);

    for (int i = 0; i < n; i ++ ) {

        if (!flag && !st[i] && a[i] <= res) {
            st[i] = true;
            dfs(res - a[i], v + 1);
            st[i] = false;

            // 这个去掉 +40MS
            if (res == a[i])
                return;

            // 这个去掉，TLE。。
            if (res == MAX)
                return;

            // 这个剪枝去掉了，+100MS
            while (a[i] == a[i + 1])
                i ++ ;
        }
    }
}

int main() {
    while (cin >> n && n) {
        int sum = 0;

        for (int i = 0; i < n; i ++ ) {

            cin >> a[i];
            sum += a[i];
        }

        sort(a, a + n, cmp);

        MAX = a[0];

        // 剪枝：如果最长的长度大于剩余所有长度和，则答案就是他们的和
        //(这个去掉了也可以，耗时没有变化 = 。=，就是说不写也可以）
        if (MAX > sum - MAX) {
            cout << sum << endl;
            continue;
        }

        flag = false;

        while (!flag) {
            // 剪枝： 如果所有长度总和 对 目标长度 取模不为0 ，则目标长度一定不是答案，这个必须有
            // 这个如果去掉，耗时增多不说，对后面剪枝影响，会导致WA
            while (sum % MAX != 0)
                MAX ++ ;

            memset(st, false, sizeof st);
            dfs(MAX, 0);

            if (flag)
                break;
            MAX ++ ;
        }

        cout << MAX << endl;
    }

    return 0;
}