[BFS]简单例题，模板

#include<iostream>
#include<queue>
using namespace std;
int a[100][100], v[100][100];//地图，是否访问过数组标记
struct point//定义一个结构体，存放当前的坐标和步数
{
    int x, y, step;
};
queue<point>r;//定义一个队列
int dx[] = {0,1,0,-1};//代表点可移动的四个方向
int dy[] = {1,0,-1,0};
int main()
{
    int n, m, startx, starty, p, q;//地图的大小，起点坐标，终点坐标
    cin >> n >> m;
    for (int i = 1; i <= n; i++)//输入地图
        for (int j = 1; j <= m; j++)
            cin >> a[i][j];
    cin >> startx >> starty >> p >> q;//输入起点，终点
    //BFS
    point start;//定义一个point类型的变量，存储起点，以及步数，以便我们可以将起点和步数压入队列
    start.x = startx;
    start.y = starty;
    start.step = 0;
    r.push(start);//将起点，以及起点的步数压入队列
    v[startx][starty] = 1;//访问过起点，所以标记为1
    int flag = 0;
    while (!r.empty())//当队列不为空的时候
    {
        int x = r.front().x;//拿出队首的具体变量，x,y,step，以便后面使用
        int y = r.front().y;
        if (x == p && y == q)//结束
        {
            flag = 1;
            cout << r.front().step;
            break;
        }
        //四个方向
        for (int i = 0; i < 4; i++)
        {
            int tx = x + dx[i];
            int ty = y + dy[i];
            if (a[tx][ty] == 1 && v[tx][ty] == 0)//判断是否为正常可走坐标
            {
                point tmp;//定义一point类型的变量，以便可以将下一步的tx,ty,step+1,压入队列
                tmp.x = tx;
                tmp.y = ty;
                tmp.step = r.front().step + 1;//步数加1
                r.push(tmp);//将新的点，步数压入队列

            }
        }
        r.pop();//新的点压入队列后，旧的首元素可以删除
    }
    if (flag == 0)
        cout << "NO ANSWER!";
    return 0;
}

over~欢迎讨论

最后

以上就是冷傲芝麻为你收集整理的[BFS]简单例题，模板的全部内容，希望文章能够帮你解决[BFS]简单例题，模板所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。