扫二维码与项目经理沟通
我们在微信上24小时期待你的声音
解答本文疑问/技术咨询/运营咨询/技术建议/互联网交流
图描述的是一些个体之间的关系。与线性表之间和二叉树之间不同的是，这些个体之间即不是前驱后继的顺序关系，也不是祖先后代的层次关系，而是错综复杂的网状关系。在图中一个比较重要的算法就是，小编接下来将要介绍的DFS算法。
下面通过一个具体的例子来介绍DFS算法——用DFS算法求联通块。
问题描述如下：油田（Oil Deposits UVa 572）
输入一个m行n列的字符矩阵，统计字符的“@”组成多少个八联块。如果两个字符“@”所在的格子相邻（横，竖，对角线方向）就说他们属于一个连通块。例如下图有两个八连块。
在山亭等地区，都构建了全面的区域性战略布局，加强发展的系统性、市场前瞻性、产品创新能力，以专注、极致的服务理念，为客户提供网站建设、成都网站建设 网站设计制作按需设计网站,公司网站建设,企业网站建设,成都品牌网站建设,营销型网站,成都外贸网站制作,山亭网站建设费用合理。
#include
#include
const int maxn=100+5;
char pic[maxn][maxn];
int m,n,idx[maxn][maxn];
void dfs(int r,int c,int id)
{
if(r<0||r>=m||c<0||c>=n) return;//“出界”的格子
if(idx[r][c]>0||pic[r][c]!='@') return;//不是@或者已经访问过的格子
idx[r][c]=id;//联通分量编号
for(int dr=-1;dr<=1;dr++)
for(int dc=-1;dc<=1;dc++)
if(dr!=0||dc!=0) dfs(r+dr,c+dc,id);
}
int main()
{
while(scanf("%d%d",&m,&n)==2&&m&&n)
{
for(int i=0;i 这道题目的算法有个好听的名字：种子填充（floodfill）。有兴趣的读者，可以在网络上查找相关资源。
我们在微信上24小时期待你的声音
解答本文疑问/技术咨询/运营咨询/技术建议/互联网交流
微信二维码
移动版官网