个人记录–BFS题

传教士与野蛮人

//定义了一个Node结构体，包含三个整数字段：lm（左岸的传教士数量），ls（左岸的野人数量），以及step（到达当前状态所需的步骤数）。
struct Node {
    int lm;
    int ls;
    int step;
};

//L[i][j][k] 表示在左岸有i个传教士和j个野人还有船所在位置的状态。
//当i为0或等于n（传教士全部在一边），或i等于j时，该状态被标记为1；否则，标记为0。
void init(int n) {
    int i, j;
    for (i = 0; i <= n; ++i) {
        for (j = 0; j <= n; ++j) {
            if (i == 0 || i == n) {
                L[i][j][0] = L[i][j][1] = 1;
            } else if (i == j) {
                L[i][j][0] = L[i][j][1] = 1;
            } else {
                L[i][j][0] = L[i][j][1] = 0;
            }
        }
    }
}

int bfs(int n, int m) {
    Node queue[1000];
    int L[n + 1][n + 1][2];
    init(n);
    
    Node cur;
    int MinStep = -1;
    int head = 0, tail = 0;
    
    queue[tail].lm = n;
    queue[tail].ls = n;
    queue[tail++].step = 0;
    L[n][n][0] = 0;
    
    while (head < tail) {
        cur = queue[head++];
        //终止条件：满足条件（cur.step 是奇数，且左岸无传教士和野人），更新MinStep并跳出循环。
        if (cur.step % 2 == 1 && cur.lm == 0 && cur.ls == 0) {
            MinStep = cur.step;
            break;
        }
        //状态转移：检查新状态是否合法且未被访问过。如果是，则将新状态加入队列并更新 L 数组。
        for (i = m; i >= 0; i--) {
            for (j = m - i; j >= 0; j--) {
                if ((i + j > 0) && (i >= j || i == 0)) {
        //i + j > 0 确保每次至少有一个人移动;i >= j 确保移动的传教士数量不少于野人数量;i == 0 允许所有移动的人都是野人
                    if (cur.step % 2 == 0) { //只有船在左岸才运
                        if (i > cur.lm || j > cur.ls || L[cur.lm - i][cur.ls - j][1] == 0) continue;
                        //不能超过左岸实际上存在的数量；访问过的状态跳过
                        else {
                            L[cur.lm - i][cur.ls - j][1] = 0;
                            queue[tail].lm = cur.lm - i;
                            queue[tail].ls = cur.ls - j;
                            queue[tail++].step = cur.step + 1;
                        }
                    }
                }
            }
        }
    }
    return MiniStep;
};

Tank

#include <iostream>

using namespace std;

bool visit[9][9][9][9] = {0};
int s1i, s1j, s2i, s2j, e1i, e1j, e2i, e2j;
int map[9][9] = {0};// 没按题目，题目是N*M，反正自己测试

int dir[9][2] = {{0, -1}, {-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, 0}};
int head = 1, tail = 1;

struct tag {
    int x1;
    int y1;
    int x2;
    int y2;
    int step;
} queue[100000];

// 不撞墙
bool isValid(int x, int y) {
    return map[x][y] != -1;
}

// 不相邻
bool isSafe(int x1, int y1, int x2, int y2) {
    return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2) > 2;
}

int bfs() {
    //初始化
    queue[tail++] = {s1i, s1j, s2i, s2j, 0};
    visit[s1i][s1j][s2i][s2j] = 1;

    while (head < tail) {
        tag cur = queue[head++];
        if (cur.x1 == e1i && cur.y1 == e1j && cur.x2 == e2i && cur.y2 == e2j) {
            return cur.step;
        }

        for (int k1 = 0; k1 < 9; k1++) {
            int x1 = cur.x1 + dir[k1][0];
            int y1 = cur.y1 + dir[k1][1];
            if (!isValid(x1, y1)) continue;

            for (int k2 = 0; k2 < 9; k2++) {
                int x2 = cur.x2 + dir[k2][0];
                int y2 = cur.y2 + dir[k2][1];
                if (!isValid(x2, y2)) continue;
                if (!isSafe(x1, y1, x2, y2)) continue;
                if (visit[x1][y1][x2][y2]) continue;

                visit[x1][y1][x2][y2] = 1;
                queue[tail++] = {x1, y1, x2, y2, cur.step + 1};
            }
        }
    }
    return -1;
}

int main() {
    // 初始化地图（用于验证的，随便创建的地图）
    for (int z = 0; z <= 9; z++) {
        map[0][z] = -1;
        map[z][0] = -1;
        map[9][z] = -1;
        map[z][9] = -1;
    }

    cout << "Please input s1i, s1j, s2i, s2j:";
    cin >> s1i >> s1j >> s2i >> s2j;
    cout << "Please input e1i, e1j, e2i, e2j:";
    cin >> e1i >> e1j >> e2i >> e2j;

    int s = bfs();
    cout << "The minimum seconds = " << s << endl;

    return 0;
}