23-5-20--bfs--bfs模板

daniel350-wang / 2023-06-01 / 原文

#include <iostream>
#include <queue>
using namespace std;
struct node {
    int x,y;
    int step;
}st,ed;
const int maxn=100;
int n,m;//图的边界
int gx,gy;//终点位置 
int book[maxn][maxn];//记录位置是否走过 
int a[maxn][maxn];//存放图的内容

//以四个方向为例,上下左右 
int dx[4] = {0,0,-1,1};
int dy[4] = {1,-1,0,0};

int bfs(int x,int y)
{
    queue <node> q;//开一个队列
    
    // 对起点初始化
    st.x = x;
    st.y = y;
    st.step = 0;  // 初始层次为 0
    
    //memset(vis, false, sizeof(vis));
    vis[x][y] = 1;  // 标记初始位置已被走过
    q.push(st);
    
    while(!q.empty())  // 直到队列为空 或 找到终点后，终止循环
    {
        st = q.front();  // 将起点更新为队列中的第一个结构
        q.pop();  // 然后将队列中第一个结构删除
        
        // 找到终点，就结束函数，并返回此时层数
        if(st.x==gx && st.y==gy)
            return st.step;
        
        for(int i=0; i<4; i++)
        {
            ed.x = st.x + dx[i];
            ed.y = st.y + dy[i];
            ed.step = st.step + 1;  //层数加一
            
            // 若该位置已走过，则进入下一循环，避免重复
            // 若超出边界，则进入下一循环
            // 其中 n、m 为边界
            if(vis[ed.x][ed.y] || map[ed.x][ed.y]=='题目条件' || ed.x<0 || ed.x>=n || ed.y<0 || ed.y>=m)
                continue;
—        if(vis[ed.x][ed.y] || map[ed.x][ed.y]=='题目条件' || ed.x<0 || ed.x>=n || ed.y<0 || ed.y>=m)
                continue;
            
            vis[ed.x][ed.y] = 1; //标记该位置已走过
            
            // 若还未到终点，则将其放入队列，变成下次调用的起点
            q.push(ed);
        }
    }
    return -1;  // 若找不到终点，则按题目要求返回特定值

}

int main()
{
    int sx, sy;   //起点
    scanf("%d %d", &n, &m);    //读入边界
    scanf("%d %d", &sx, &sy);  //读入起点
    scanf("%d %d", &gx, &gy);  //读入终点
    
    for(int i=0; i<n; i++)
        for(int j=0; j<m; j++)
            scanf("%c", &a[i][j]);
    
    if(sx==gx && sy==gy)
        printf("0\n");
    else
        printf("%d\n", bfs(sx, sy));
    return 0;
}