用dfs求联通块（UVa572）

一、题目

输入一个m行n列的字符矩阵，统计字符“@”组成多少个八连块。如果两个字符所在的格子相邻（横、竖、或者对角线方向），就说它们属于同一个八连块。

二、解题思路

和前面的二叉树遍历类似，图也有DFS和BFS遍历。由于DFS更容易编写，一般用DFS找联通块：从每个“@”格子出发，递归遍历与之相邻的“@”格子，标记相同的“联通分量标号”。这样在访问之前需检查它是否已经有了编号，从而避免一个格子访问多次。

三、代码实现

 #include<stdio.h>

 #include<iostream>

 using namespace std;

 const int maxn =  + ;

 char field[maxn][maxn];

 int N, M;

 void dfs(int x, int y)

 {

     field[x][y] = '*';                      //这里通过把“@”换成“*”，从而避免重复

     for (int dx = -; dx <= ; dx++)

         for (int dy = -; dy <= ; dy++)

         {

             int nx = x + dx; int ny = y + dy;

             if (nx >=  && nx < N && ny >=  && ny < M && field[nx][ny] == '@')

                 dfs(nx, ny);

         }

     return;

 }

 void slove()

 {

     int res = ;

     for (int i = ; i < N; i++)

         for (int j = ; j < M; j++)

         {

             if (field[i][j] == '@')

             {

                 dfs(i, j);

                 res++;          //遍历完一个连通分量，答案加一

             }

         }

     printf("%d\n", res);

 }

 int main()

 {

     while (scanf("%d%d", &N, &M) ==  && N)

     {

         for (int i = ; i < N; i++)

             for (int j = ; j < M; j++)

                 cin >> field[i][j];

         slove();

     }

     return ;

 }

巴特西

用dfs求联通块（UVa572）

最新文章

热门文章