깊이 우선 검색 (DFS) 과 넓이 우선 검색 (BFS)

T1: 장기판 문제 POJ - 1321 POJ - 1321
분석: 본 문 제 는 바둑판 의 분포 와 낙자 수 를 제시 하여 바둑돌 이 서로 다른 열 에 놓 이지 않 는 상황 에서 몇 가지 낙자 방식 이 있 는 지 구 해 보 자.
이 문 제 는 DFS 알고리즘 을 이용 하여 재 귀 함 수 를 만 듭 니 다.첫 번 째 줄 의 첫 번 째 열 위 치 를 열 에서 스 캔 하기 시 작 했 습 니 다. 적당 한 위 치 를 찾 으 면 떨 어 뜨 린 다음 에 이 열 을 표시 하면 이 열 을 다시 떨 어 뜨 릴 수 없다 는 것 을 표시 합 니 다.
이렇게 한 후에 앞 에 떨 어 진 자 리 를 오른쪽으로 한 명 아래로 옮 기 고 이 새로운 위치 에서 재 귀 함 수 를 호출 합 니 다.바둑 알 을 모두 다 쓰 면 방안 수 에 1 을 더 합 니 다.
PS: 전체 과정의 깊이 를 이해 하고 검색 방향 을 우선 시 하 는 것 이 코드 를 이해 하 는 데 유리 합 니 다.

 1 #include
 2 #include
 3 using namespace std;
 4 const int maxn=10;
 5 char chessboard[maxn][maxn];
 6 bool visit[maxn];//               
 7 int ans;//     
 8 int k;//      
 9 int n;//        
10 int DFS(int row,int nums_of_chess){//row     ，nums_of_chess            
11     if(nums_of_chess==k){
12         ans++;
13         return 0;
14     }
15     for(int i=row;i)
16         for(int j=0;j)
17             if(!visit[j]&&chessboard[i][j]=='#'){//          ，            
18                 visit[j]=true;//       
19                 DFS(i+1,nums_of_chess+1);//       
20                 visit[j]=false;//        ，        ，                 
21             }
22     return 0;
23 }
24 int main(){ 
25     while(cin>>n>>k){
26         if(n==-1&&k==-1) break;
27         memset(visit,false,sizeof(visit));
28         for(int i=0;i)
29         for(int j=0;j)
30             cin>>chessboard[i][j];
31         ans=0;
32         DFS(0,0);
33         cout<endl;
34     }
35     return 0;
36 }

 
T2: 미로 문제 POJ - 3984 POJ - 3984
문제 분석: 이것 은 미로 문제 로 가장 짧 은 노선 과 기록 이동 경로 가 결 합 된 문제 로 이해 할 수 있다.최 단 노선 문 제 는 일반적으로 BFS 를 이용 하여 광범 위 하 게 우선 검색 하 는 방법 으로 해결한다.하지만 이 문 제 는 이동 경 로 를 기록 하 라 는 요구 도 추가 됐다.
따라서 구조 체 를 구축 하 는 것 은 모든 위 치 를 대표 하고 구조 체 에 dir 배열 을 포함 하 는 것 은 모든 방향 을 기록 하기 위 한 것 이다.구조 BFS 함 수 는 마지막 위치의 구조 체 를 되 돌려 줍 니 다. 이 구조 체 중의 dir 배열 을 통 해 초기 위치 (0, 0) 좌 표를 맞 춥 니 다.
매번 이동 하 는 좌 표를 구하 고 출력 할 수 있다.
코드 는 다음 과 같 습 니 다:

 1 #include
 2 #include
 3 #include
 4 #include
 5 using namespace std;
 6 int maze[5][5];
 7 bool visit[5][5];
 8 int dx[4]={1,-1,0,0};//             
 9 int dy[4]={0,0,1,-1};
10 struct Node{
11     int x,y;//       x,y  
12     int length;//      
13     int dir[30];//              
14 };
15 Node &BFS(){
16     queue que;
17     Node rec,next;
18     rec.x=0;//           
19     rec.y=0;
20     rec.length=0;
21     que.push(rec);
22     while(que.size()){
23         rec=que.front();
24         que.pop();
25         if(rec.x==4&&rec.y==4) return rec;//         
26         for(int i=0;i<4;i++)
27         {
28             int nx=rec.x+dx[i];//          
29             int ny=rec.y+dy[i];
30             if(maze[nx][ny]==0&&nx>=0&&nx<5&&ny>=0&&ny<5&&!visit[nx][ny])//             
31             {    visit[nx][ny]=true;
32                 next=rec;//    next rec   ，                 
33                 next.x=nx;
34                 next.y=ny;
35                 next.length=rec.length+1;
36                 next.dir[rec.length]=i;
37                 que.push(next);
38             } 
39         }
40     }
41 } 
42 int main(){
43     for(int i=0;i<5;i++)
44         for(int j=0;j<5;j++)
45             cin>>maze[i][j];
46     memset(visit,false,sizeof(visit));
47     Node last=BFS();
48     printf("(0, 0)
");
49     int x=0,y=0;
50     for(int i=0;i)
51     {
52         
53         x+=dx[last.dir[i]];
54         y+=dy[last.dir[i]];
55         printf("(%d, %d)
",x,y);
56     }
57     return 0;
58 }

 
T3 POJ-2251 
문제 분석: 이것 은 미로 의 가장 짧 은 경로 문제 로 예전 의 2 차원 미 로 를 3 차원 미로 로 만 들 었 을 뿐이다.이전의 2 차원 bfs 알고리즘 을 3 차원 으로 연장 하면 된다.

 1 #include
 2 #include
 3 #include
 4 #include
 5 using namespace std;
 6 struct Node{
 7     int x,y,z;
 8 };
 9 char space[35][35][35];
10 int dis[35][35][35];
11 int L,R,C;
12 int sx,sy,sz;
13 int ex,ey,ez;
14 int dx[]={1,-1,0,0,0,0};
15 int dy[]={0,0,1,-1,0,0};
16 int dz[]={0,0,0,0,1,-1};
17 int bfs(){
18     queue que;
19     Node t;
20     t.x=sx;
21     t.y=sy;
22     t.z=sz;
23     que.push(t);
24     while(que.size()){
25         Node p=que.front();
26         que.pop();
27         if(p.x==ex&&p.y==ey&&p.z==ez) return dis[ex][ey][ez];
28         for(int i=0;i<6;i++){
29             int nx,ny,nz;
30             nx=p.x+dx[i];
31             ny=p.y+dy[i];
32             nz=p.z+dz[i];
33             if(nx>=0&&nx=0&&ny=0&&nz0&&space[nx][ny][nz]!='#'){
34                 dis[nx][ny][nz]=dis[p.x][p.y][p.z]+1;
35                 t.x=nx;t.y=ny;t.z=nz;
36                 que.push(t);
37             }
38         }
39     }
40     return dis[ex][ey][ez];
41 }
42 
43 
44 int main(){
45     while(cin>>L>>R>>C){
46         memset(dis,0,sizeof(dis));
47         memset(space,0,sizeof(space));
48         if(L==0&&R==0&&C==0) break;
49         for(int i=0;i)
50             for(int j=0;j)
51                 for(int k=0;k)
52                 {
53                     cin>>space[i][j][k];
54                 }
55     
56     for(int i=0;i)
57             for(int j=0;j)
58                 for(int k=0;k)
59                 {
60                     if(space[i][j][k]=='S') {
61                         sx=i;
62                         sy=j;
63                         sz=k;
64                     }
65                     if(space[i][j][k]=='E') {
66                         ex=i;
67                         ey=j;
68                         ez=k;
69                     }
70                 }
71          int ans= bfs();
72         if(ans==0)  printf("Trapped!
");
73         else printf("Escaped in %d minute(s).
",ans);
74     }
75     return 0;
76 }

 
 T4POJ-3278
문제 분석: 이것 은 1 차원 에서 가장 짧 은 경 로 를 찾 는 문제 이지 만 출발점 좌표 의 변환 은 왼쪽으로 한 걸음, 오른쪽으로 한 걸음, 좌표 * 2 세 가지 방식 이 있다.따라서 세 개의 if 문 구 를 이용 하여 bfs 를 진행 하면 됩 니 다.전역 배열 의 초기 값 은 0 이 므 로 memset () 을 사용 하지 않 습 니 다.
 

 1 #include
 2 #include
 3 #include
 4 using namespace std;
 5 const int maxn=100005;
 6 int N,K;
 7 int visit[maxn];
 8 int step[maxn];
 9 bool let(int u)  
10 {  
11     if(u<0||u>100000||visit[u])  
12         return 0;  
13     return 1;  
14 }  
15 queue<int> que;
16 int bfs(){
17     que.push(N);
18     while(que.size()){
19         int u;
20         u=que.front();
21         que.pop();
22         if(u==K)  {
23             cout<<visit[u];
24             return 0;
25         }
26         if(let(u+1)) {
27             visit[u+1]=visit[u]+1;
28             que.push(u+1);
29         }
30         if(let(u-1)) {
31             visit[u-1]=visit[u]+1;
32             que.push(u-1);
33         }
34         if(let(2*u)) {
35             visit[2*u]=visit[u]+1;
36             que.push(2*u);
37         }
38     }
39 }
40 int main(){
41     cin>>N>>K;
42     bfs();
43     return 0;
44 } 

 
T5   HDU-1312
문제 분석: 간단 한 DFS 검색 문제 입 니 다. 여러 그룹 이 입력 되 어 있 기 때문에 입력 할 때마다 태그 배열 visit 를 비 워 두 는 것 을 기억 하 십시오.

 1 #include
 2 #include
 3 using namespace std;
 4 const int maxw=25;
 5 const int maxh=25;
 6 int dx[4]={1,-1,0,0};
 7 int dy[4]={0,0,1,-1}; 
 8 char map[maxw][maxh];
 9 int visit[maxw][maxh];
10 int W,H,ans;
11 void dfs(int x,int y){
12     for(int i=0;i<4;i++){
13         int nx=x+dx[i];
14         int ny=y+dy[i];
15         if(nx>=0&&nx=0&&ny'.'&&!visit[nx][ny])
16             {
17                 ans++;
18                 visit[nx][ny]=1;
19                 dfs(nx,ny);
20             }
21     }
22         
23 }
24 int main(){
25     while(cin>>H>>W){
26         memset(visit,0,sizeof(visit));
27         int sx,sy;
28         ans=1;
29         if(W==0&&H==0) break;
30         for(int i=0;i)
31             for(int j=0;j)
32                 cin>>map[i][j];
33         for(int i=0;i)
34             for(int j=0;j)
35                 if(map[i][j]=='@'){
36                     sx=i;
37                     sy=j;
38                     break;
39                 }
40         dfs(sx,sy);
41         cout<endl;
42     }
43     return 0;
44 } 

 
다음으로 전송:https://www.cnblogs.com/FrankYu-/p/9637098.html