Adament Cabin

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

C++ 深度优先搜索

2021年11月4日 565ヒート 0お気に入り 0コメント

深度优先搜索算法(英语:Depth-First-Search,DFS)是一种用于遍历或搜索树或图的算法。这个算法会尽可能深的搜索树的分支。当节点v的所在边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点,则选择其中一个作为源节点并重复以上过程,整个进程反复进行直到所有节点都被访问为止。这种算法不会根据图的结构等信息调整执行策略。

  1. 首先将根节点放入stack中。
  2. 从stack中取出第一个节点,并检验它是否为目标。
    如果找到目标,则结束搜寻并回传结果。 否则将它某一个尚未检验过的直接子节点加入stack中。
  3. 重复步骤2。
  4. 如果不存在未检测过的直接子节点。
    将上一级节点加入stack中。
  5. 重复步骤2。
    重复步骤4。
  6. 若stack为空,表示整张图都检查过了——亦即图中没有欲搜寻的目标。结束搜寻并回传“找不到目标”。
#include <iostream>
using namespace std;
int startx,starty,endx,endy;
int mi=999999;
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
int m[100][100],v[100][100];
bool found=false;
void DFS(int x,int y,int step){
    if(x==endx&&y==endy) {mi=min(step,mi);found=true;return;}
    else{
        for(int k=0;k<4;k++){
            int nextx=x+dx[k];
            int nexty=y+dy[k];
            if(m[nextx][nexty]==1&&v[nextx][nexty]==0){
                v[nextx][nexty]=1;
//              printf("I found %d %d and step here is %dn",nextx,nexty,step+1);
                DFS(nextx,nexty,step+1);
                v[nextx][nexty]=0;
            }
        }
    }
}
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;}
    cin >> startx >> starty >> endx >> endy;
    v[startx][starty]=1;
    DFS(startx,starty,0);
    if(found==true) cout << mi << endl;
    else 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
キャンセル

カテゴリー
  • アルゴリズム / 5篇
  • Linux / 5篇
  • NEUQACM / 9篇
  • Problems / 3篇
  • 日常 / 2篇
  • 日本語 / 2篇
  • ゲーム / 1篇
  • コンピューター / 22篇
  • ドキュメント / 4篇
タグ
Magisk ArchLinux C/C++/C# Learning Arcaea Physics LaTex
ヤツメ穴
https://www.adament.xyz/wp-content/uploads/2022/03/ヤツメ穴(BGM).mp3
クリスタルグラビティ
https://www.adament.xyz/wp-content/uploads/2022/08/CrystalGravity.mp3

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