Adament Cabin

  • コンピューター
    • アルゴリズム
    • Linux
    • Problems
    • AI
  • 日本語を勉強
  • ACG
    • 見られている番組
    • ゲーム
  • 日常
  • 雑貨
    • ドキュメント
    • 資源
    • 治療センター
  • リンク
  • ブランチサイト
  • Japanese
    • Chinese
Adament Cabin
恋厨症候群第二治療センター
  1. 首页
  2. コンピューター
  3. アルゴリズム
  4. 正文

C++ 广度优先搜索

2021年10月21日 1372ヒート 0お気に入り 0コメント

广度优先搜索算法(英语:Breadth-First Search,缩写为BFS),又译作宽度优先搜索,或横向优先搜索,是一种图形搜索算法。简单的说,BFS是从根节点开始,沿着树的宽度遍历树的节点。如果所有节点均被访问,则算法中止。广度优先搜索的实现一般采用open-closed表。

BFS是一种暴力搜索算法,目的是系统地展开并检查图中的所有节点,以找寻结果。换句话说,它并不考虑结果的可能地址,彻底地搜索整张图,直到找到结果为止。

  1. 首先将根节点放入队列中。
  2. 从队列中取出第一个节点,并检验它是否为目标。如果找到目标,则结束搜索并回传结果。否则将它所有尚未检验过的直接子节点加入队列中。
  3. 若队列为空,表示整张图都检查过了——亦即图中没有欲搜索的目标。结束搜索并回传“找不到目标”。
  4. 重复步骤2。
#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;
}
タグ: C/C++/C#
更新日:2022年4月21日

BiyiAdopac

社会ごみ

Like
< 前の投稿
次の投稿 >

コメント

razz evil exclaim smile redface biggrin eek confused idea lol mad twisted rolleyes wink cool arrow neutral cry mrgreen drooling persevering
キャンセル

カテゴリー
  • AI / 1篇
  • アルゴリズム / 5篇
  • Linux / 6篇
  • Problems / 3篇
  • 日常 / 1篇
  • 日本語 / 2篇
  • ゲーム / 1篇
  • コンピューター / 14篇
  • ドキュメント / 4篇
タグ
Physics Arcaea ArchLinux Learning C/C++/C# Magisk LaTex AI
The World of Scarlet
https://www.adament.xyz/wp-content/uploads/2024/10/the-world-of-scarlet-Piano.mp3

COPYRIGHT © 2025 adament.xyz. ALL RIGHTS RESERVED.
このサイトにとって重要ではありませんが、それでも必要な プライバシーポリシー