首页 > 代码库 > 深度搜索应用之黑白图像(非递归)

深度搜索应用之黑白图像(非递归)

2024-07-05 15:17:17   222人阅读

深度搜索应用之黑白图像(非递归)

前言：

　　使用深度搜索，有两个方法：递归，栈。本质是栈。

　　递归有一个缺陷，栈溢出。栈有一个缺陷,程序相对递归更复杂。

练习题：

 

　　输入一个n*n的黑白图像（1表示黑色，0表示白色），任务是统计其中八连块的个数。如果两个黑格子有公共边或者公共顶点，就说它们属于同一个八连块。（题意是让求连在一起的块有几个，图见书本）

 

 

 

使用递归求解：点这里

使用栈求解：

 

 1 #include <iostream>
 2 #include <memory.h>
 3 #include <stack>
 4 using namespace std;
 5 const int MAXN=8;
 6 
 7 typedef struct
 8 {
 9     int x;
10     int y;
11 } node;
12 
13 stack<node> stack_temp;
14 node node_temp;
15 void push_value(int x,int y)
16 {
17     node_temp.x=x;
18     node_temp.y=y;
19     stack_temp.push(node_temp);
20 }
21 
22 int mat[MAXN][MAXN]= {0,0,0,0,0,0,0,0,
23                       0,1,0,0,1,0,0,0,
24                       0,0,0,1,0,1,0,0,
25                       0,0,0,0,0,0,0,0,
26                       0,1,1,0,0,0,0,0,
27                       0,1,1,1,0,0,0,0,
28                       0,0,1,0,1,0,0,0,
29                       0,0,0,0,0,0,0,0
30                      },vist[MAXN][MAXN]= {0};
31 
32 void dfs(int x,int y)
33 {
34     push_value(x,y);
35     vist[x][y]=1;
36     bool flag_break=false;
37     bool flag_for_over=false;
38     while(!stack_temp.empty())
39     {
40         int temp_x=stack_temp.top().x,temp_y=stack_temp.top().y;
41 
42         /**< 对周围的8个结点进行遍历 */
43         for(int i=temp_x-1,last_x = temp_x+1; i<=last_x; ++i)
44         {
45             for(int j=temp_y-1,last_y = temp_y+1; j<=last_y; ++j)
46             {
47                 if(mat[i][j]&&!vist[i][j])
48                 {
49                     cout<<"("<<i<<","<<j<<")"<<endl;
50                     vist[i][j]=1;
51                     push_value(i,j);
52                     flag_break=true;
53                     break;
54                 }
55             }
56             /**< 用于标志一个有效结点，方便对下周围的结点进行遍历 */
57             if(flag_break)
58             {
59                 flag_break=false;
60                 break;
61             }
62 
63             /**< 用于标志一个for循环是否结束,用于判断出栈的标志 */
64             if(i>=last_x)
65             {
66                 flag_for_over=true;

67                 break;
68             }
69         }
70 
71         /**< 若一个循环结束，则踢出一个结点 */
72         if(flag_for_over)
73         {
74             stack_temp.pop();
75             flag_for_over=false;
76         }
77     }
78     return ;
79 }
80 
81 int main()
82 {
83     int count_=0;
84     memset(vist,0,sizeof(vist));
85     for(int i=1; i<=6; ++i)
86     {
87         for(int j=1; j<=6; ++j)
88         {
89             if(mat[i][j] && !vist[i][j])
90             {
91                 ++count_;
92                 dfs(i,j);
93             }
94         }
95     }
96     cout<<count_<<endl;
97     return 0;
98 }

 

参考资料：点这里

 


联系
我们