广度优先搜索算法(英语:Breadth-First Search,缩写为BFS),又译作宽度优先搜索,或横向优先搜索,是一种图形搜索算法。简单的说,BFS是从根节点开始,沿着树的宽度遍历树的节点。如果所有节点均被访问,则算法中止。广度优先搜索的实现一般采用open-closed表。
BFS是一种暴力搜索算法,目的是系统地展开并检查图中的所有节点,以找寻结果。换句话说,它并不考虑结果的可能地址,彻底地搜索整张图,直到找到结果为止。
#include <iostream>
#include <queue>
using namespace std;
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
int m[100][100],v[100][100];
struct road{
    int x;
    int y;
    int step;
};
queue<road> ma;
int main(){
    int a,b;
    cin >> a >> b;
    int nu;
    for(int i=1;i<=a;i++) for(int j=1;j<=b;j++) {cin >> nu;m[i][j]=nu+1;}
    int startx,starty,endx,endy;
    cin >> startx >> starty >> endx >> endy;
    road start;
    start.x=startx;
    start.y=starty;
    start.step=0;
    ma.push(start);
    v[startx][starty]=1;
    bool flag=0;
    while(!ma.empty()){
        road next;
        start=ma.front();
        if(start.x==endx&&start.y==endy){cout << start.step << endl;flag=1;break;}
        for(int k=0;k<4;k++){
            next.x=start.x+dx[k];
            next.y=start.y+dy[k];
            next.step=start.step+1;
            if(m[next.x][next.y]==1&&v[next.x][next.y]==0){
                printf("I got %d %dn",next.x,next.y);
                ma.push(next);
                v[next.x][next.y]=1;
            }
        }
        ma.pop();
    }
    if(flag==0) cout << "Not Found" << endl;
    return 0;
}
文章评论