BFS——広さ優先検索

広さ優先探索は,図の完全な遍歴によって従来要求された点に達するアルゴリズムである.その対図の遍歴は波のように、各層が制定された方法で1層1層下を探している.
次のようになります.
５
５
４
２
５
５
２
4
２
３
４
2
３
4
４
１
４
1
１
２
６
７
５
３
４
3を起点としてbfs探索を行い,探索方式は毎回その上下左右の数だけを探索し,そのうち(最初の)起点より小さい数を探索する.最初は4(上)、4(右)、1(下)、2(左)しか検索されませんでしたが、そのうち2と1だけが条件を満たしているので、2と1を次の階の起点として検索し続け、これ以上検索できないまで(図には4階建てで、それぞれ4色で表されています).我々は通常,各判断が必要な起点をキューで格納し,最初は3(赤)がキューにあり,3(赤)を読み出した後,満足度の1,2(緑)をキューに加え,順次類推する.
これによりbfsは倒れた木と見なすことができ、3(赤)はその根ノードである.2,1(緑)はそのサブノードであり、2,1(青)はそれぞれ2,1(緑)のサブノードであり、2(粉)は1(青)のサブノードである.
bfsの具体的なコードを例題で理解します.
hrbust 1143泉:
ブログの問題解へのリンク:
http://blog.csdn.net/ilblue/article/details/52892373
原題リンク:
http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblem&problem_id=1143
図の中のすべての起点から到達できる起点よりも低い場所の個数を見つけることを意味します.

#include
#include
#include
#include
#include
using namespace std;
const int MAX = 1000;

struct Point{　　//        
    int x,y;
}start,zhuan,number;
int sum;
int hang,lie;
int mapp[MAX+9][MAX+9];
int gao[MAX+9][MAX+9];
int step1[4] = {1,0,-1,0};
int step2[4] = {0,1,0,-1};

int bfs(Point start) //   
{
    queue que;　　//        
    que.push(start);
    mapp[start.x][start.y] = 1;

　 while(!que.empty()){
        number = que.front();　//                   ，                       
        que.pop();

　　 for(int i = 0;i < 4;i++){
            zhuan.x = number.x+step1[i];　//               
            zhuan.y = number.y+step2[i];

　　　 if(zhuan.x<=hang && zhuan.x>=1 && zhuan.y<=lie && zhuan.y>=1 && mapp[zhuan.x][zhuan.y]!=1 && gao[start.x][start.y]>=gao[zhuan.x][zhuan.y]){
                que.push(zhuan);　　//           
                mapp[zhuan.x][zhuan.y] = 1;
                sum++;
            }
        }
    }

　 return sum;
}

void init()
{
    memset(mapp,1,sizeof(mapp));
    for(int i = 1;i <= hang;i++){
        for(int j = 1;j <= lie;j++){
            mapp[i][j] = 0;
        }
    }
    sum = 1;
}

int main()
{
    while(scanf("%d%d%d%d",&hang,&lie,&start.x,&start.y) != EOF){
        init();
        for(int i = 1;i <= hang;i++){
            for(int j = 1;j <= lie;j++){
                scanf("%d",&gao[i][j]);
            }
        }
        printf("%d
",bfs(start));
    }
    return 0;
}

この問題で対数のカウントは,キューに押し込むたびにカウンタに1を加えるだけであることがわかる.bfsの利点は,層数に関する問題ではdfsよりも速度が速いことであるが,bfsは層数が高いほど時間が非常に大きくなり,剪断操作が必要である.