忘了标题-----简单的bfs

BFS

bfs代码：

int BFS()
{
    node now,next;
    queue<node>q;//队列
    now.x=x;
    now.y=y;
    now.step=0;
    q.push(now);//初始点入队
    while(!q.empty())
    {
        now=q.front();
        q.pop();
        if(a[now.x][now.y]=='C')
        {
            count=now.step;
            return count;
        }
        for(i=0;i<4;i++)//p的所有邻接点
        {
            next=now;
            next.x+=dir[i][0];
            next.y+=dir[i][1];
            if(next.x>=0&&next.x<r&&next.y>=0&&next.y<c&&a[next.x][next.y]!='*'&&vis[next.x][next.y]==0)
            {
                vis[next.x][next.y]=1;
                next.step=now.step+1;
                q.push(next);
            }
        }
    }
    return -1;
}

完整代码：

#include<stdio.h>
#include<queue>
using namespace std;
int dir[4][2]={1,0,-1,0,0,1,0,-1};//方向数组
int vis[111][111];//标记数组
char a[111][111];//存路径的数组
int r,c,x,y,count,i;
struct node
{
    int x;
    int y;
    int step;
};
int BFS()
{
    node now,next;
    queue<node>q;//队列
    now.x=x;
    now.y=y;
    now.step=0;
    q.push(now);//初始点入队
    while(!q.empty())
    {
        now=q.front();
        q.pop();
        if(a[now.x][now.y]=='C')
        {
            count=now.step;
            return count;
        }
        for(i=0;i<4;i++)//p的所有邻接点
        {
            next=now;
            next.x+=dir[i][0];
            next.y+=dir[i][1];
            if(next.x>=0&&next.x<r&&next.y>=0&&next.y<c&&a[next.x][next.y]!='*'&&vis[next.x][next.y]==0)
            {
                vis[next.x][next.y]=1;
                next.step=now.step+1;
                q.push(next);
            }
        }
    }
    return -1;
}
int main()
{
    int i,j,ct;
    scanf("%d%d",&r,&c);
    for(i=0;i<r;i++)
        scanf("%s",&a[i]);
    for(i=0;i<r;i++)
        for(j=0;j<c;j++)
            if(a[i][j]=='B')
            {
                x=i;
                y=j;
            }
    ct=BFS();
    printf("%d\n",ct);
    return 0;
}