C++ 广搜算法，算法问题

、

人物每一步移动只能按照上下左右方向移动，不能进入障碍格子（可以通过有其他人物的格子）。

以下是 C++ 广搜算法的代码实现，其中使用了一个二维数组来表示游戏地图，用 isValidMove 函数来判断人物是否能移动到指定位置，用 search 函数来实现广搜算法：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAX_ROW = 10;
const int MAX_COL = 10;
const int MIN_MOVE = -1;
const int MAX_MOVE = 1;
const int MAP_WIDTH = 20;
const int MAP_HEIGHT = 10;

struct Character {
    int x, y;
};

bool isValidMove(int x, int y, int dx, int dy) {
    return x >= 0 && x < MAP_WIDTH && y >= 0 && y < MAP_HEIGHT;
}

void search(Character* character, vector<Character*>& path, bool (*isValidMove)(int, int, int, int)) {
    if (*character == NULL) return;
    path.push_back(*character);
    if (*character->x == *(path.back()->x) && *character->y == *(path.back()->y)) {
        cout << "Found path: ";
        for (int i = path.size() - 1; i >= 0; i--) {
            cout << path[i]->x << ", " << path[i]->y << " ";
        }
        cout << endl;
        return;
    } else {
        for (int i = 0; i < MAX_MOVE + 1; i++) {
            int newX = (*character->x + dx * i) % (MAP_WIDTH * 2);
            int newY = (*character->y + dy * i) % (MAP_HEIGHT * 2);
            if (isValidMove(newX, newY, dx, dy) && path.find(new Character{newX, newY}) == path.end()) {
                character->x = newX;
                character->y = newY;
                search(character, path, isValidMove);
                if (!isValidMove(newX, newY, dx, dy)) break;
            }
        }
    }
    path.pop_back();
}

int main() {
    vector<Character*> path;
    int startX = MAP_WIDTH / 2;
    int startY = MAP_HEIGHT / 2;

该回答引用ChatGPT
这是一道广搜算法的题目，可以使用C++的STL库里的queue来实现。

首先，我们定义一个结构体来表示每个格子的信息，包括坐标和当前的步数。

C++
struct node{
    int x, y;//坐标
    int step;//步数
};

然后，我们定义一个bfs函数来实现广搜。在bfs函数中，我们需要维护一个bool类型的v数组来记录每个格子是否访问过，还需要定义一个队列来存储待访问的格子。这里，我们通过定义一个2维数组mp来表示整个地图的情况，1代表该格子可以通过，0代表不能通过。

具体代码如下：

C++
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int maxn=1005;//地图最大大小
int mp[maxn][maxn];//用来表示地图的数组
bool v[maxn][maxn];//用来记录一个格子是否被访问过
int n,m;//地图的大小

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

int bfs(int sx,int sy,int tx,int ty){
    memset(v,false,sizeof(v));
    v[sx][sy]=true;
    queue<node> q;
    node start;
    start.x=sx;
    start.y=sy;
    start.step=0;
    q.push(start);
    int next_x,next_y;

    while(!q.empty()){
        node cur=q.front();
        q.pop();
        if(cur.x==tx&&cur.y==ty)return cur.step;
        for(int i=-1;i<=1;i++){
            for(int j=-1;j<=1;j++){
                if(!(i==0^j==0))continue;//如果i和j的差值都不为0，说明这个格子不是上下左右四个方向之一。
                next_x=cur.x+i;
                next_y=cur.y+j;
                if(next_x<1||next_x>n||next_y<1||next_y>m)continue;//下一个格子超出地图边界
                if(mp[next_x][next_y]==0)continue;//下一个格子是障碍格子
                if(v[next_x][next_y]==true)continue;//下一个格子已经被访问过
                v[next_x][next_y]=true;
                node next;
                next.x=next_x;
                next.y=next_y;
                next.step=cur.step+1;
                q.push(next);
            }
        }
    }
    return -1;//无法到达目标地点
}

int main(){
    int sx,sy,tx,ty;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)scanf("%d",&mp[i][j]);
    scanf("%d%d%d%d",&sx,&sy,&tx,&ty);
    printf("%d
",bfs(sx,sy,tx,ty));
    return 0;
}

接下来，我们对代码进行解释：

在bfs函数中，我们首先将起始节点入队列，并将其标记为已经访问过。然后，我们不断从队列取出未被访问过的节点，并将其所有相邻节点入队列。

需要注意的是，在for循环中，我们使用了一个continue语句来跳过不符合要求的格子，例如，如果当前格子已经被访问过，我们就跳过该格子；如果下一个格子是障碍格子，我们也跳过该格子。

最后，如果最终无法到达目标地点，我们返回-1。

C++一本通基础算法：广度优先搜索（BFS）

可以借鉴下
https://blog.csdn.net/zxh_minecraft/article/details/125939159

以下答案由GPT-3.5大模型与博主波罗歌共同编写：
C++广搜算法：

以下是一个简单的C++代码实现，用于解决这个问题：

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

int n, m; // 地图的行数和列数 
int sx, sy; // 起点的坐标 
int ex, ey; // 终点的坐标 
 
const int MAX_N = 100;
const int MAX_M = 100;
char map[MAX_N][MAX_M + 1]; // 地图信息 
int d[MAX_N][MAX_M]; // 距离的数组 
const int dx[4] = {-1, 0, 1, 0}; // 上下左右四个方向的坐标变化 
const int dy[4] = {0, 1, 0, -1};

// 广搜算法
int bfs() {
    queue<pair<int, int> > que;
    memset(d, -1, sizeof(d));
    que.push(make_pair(sx, sy));
    d[sx][sy] = 0;

    while (!que.empty()) {
        pair<int, int> p = que.front();
        que.pop();

        if (p.first == ex && p.second == ey) break;

        for (int i = 0; i < 4; ++i) {
            int nx = p.first + dx[i];
            int ny = p.second + dy[i];

            if (0 <= nx && nx < n && 0 <= ny && ny < m && map[nx][ny] != '#' && d[nx][ny] == -1) {
                que.push(make_pair(nx, ny));
                d[nx][ny] = d[p.first][p.second] + 1;
            }
        }
    }

    return d[ex][ey];
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        cin >> map[i];
        for (int j = 0; j < m; ++j) {
            if (map[i][j] == 'S') {
                sx = i;
                sy = j;
            } else if (map[i][j] == 'G') {
                ex = i;
                ey = j;
            }
        }
    }

    int ans = bfs();
    cout << ans << endl;

    return 0;
}

在上面的代码中，先输入地图的大小和内容，然后在地图中搜索起点和终点的位置，并通过 bfs() 函数进行广度优先搜索，查找从起点到终点需要的最短距离。搜索过程中需要用到队列、距离数组和四个方向的坐标变化。搜索时间复杂度为 $ O(nm)$，其中 n 是地图的行数，m 是地图的列数。

注：这个广搜算法示例默认只有一个人物寻找出口。如果需要多个人协同搜索，则需要用多源广搜，用多个起点来进行搜索。
如果我的回答解决了您的问题，请采纳！