BFS 시작 (위조 템플릿)

bfs 광도 우선 검색

최근에 몇 가지 검색 문제를 풀었는데, 갑자기 이런 방법이 존재하고 있다는 것을 발견하였다.비교적 기초적인 bfs 코드를 총결하였다.이 코드는 Poj3278 농부가 소를 쫓는 문제의 AC 코드입니다.

코드는 다음과 같습니다.

주로 주석 보기

#include 
#include
#include
#include
#include
using namespace std;
#define N 10000000//     
type start,aim;//type       
//start    ，aim    
struct node{
int  x;
int step;
};
//      
//1.       
//2.  
bool vis[N];
//           
queue q;
//    
void bfs()
{

    while(!q.empty())
    {
        if(q.front().x==aim)
        {
            return;
        }
        node tmp;
        //tmp        
        int X=q.front().x;
        //    X
        //          
        int Step=q.front().step;
        q.pop();
        //       
        //    
        if(X>=1&&!vis[X-1])
            //    1    ,   X >= 1
            //         
        {
        tmp.x=X-1;//    
        //      
        tmp.step=Step+1;
        vis[X-1]=1;
        //          
        //           
        q.push(tmp);
        }
        //             
        //       
        if(X1])
            //           
            //1.     
            //2.    
            //3.    ” “
        {
        tmp.x=X+1;
        tmp.step=Step+1;
        vis[X+1]=1;
        q.push(tmp);
        }
        //        
        if(X2*X])
        {
            tmp.x=2*X;
            tmp.step=Step+1;
            vis[2*X]=1;
            q.push(tmp);
        }
   }
}
int main()
{
    while(cin>>start>>aim)//     
    {
        memset(vis,0,sizeof(vis));
        //          
        while(!q.empty())q.pop();
        //             
        node ST;
        ST.x=start;
        ST.step=0;
        q.push(ST);
        //      
        //          
        bfs();
        //                  
        cout<return 0;
}
//