[算法训练-初级篇]1. 深度优先搜索

深度优先搜索:

个人理解：从第一个开始搜索，搜索其全部方向。若在搜索其中某个方向时有符合条件的元素，就以此元素再进行递归，递归时把该元素置为不符合条件，然 后又在搜索其全部方向。。。直到所有元素都遍历完。【两个for循环，一个是用于遍历所有元素，另一个遍历某个元素的所有方向】

（和广度优先搜索一样围绕某个元素遍历其所有方向，不同在于，深度优先会在发现符合条件的元素时，递归调用，层层深入，无法深入再进行下一个方向；广度则无论有无符合条件的元素，都进行下一个方向）

特点：采用递归，比较简练。

应用：（暂时不了解）

例题：（POJ  No.2386）

有一个大小为N*M的园子，雨后积起水来，八连通（八个方向）的积水被认为是连接在一起的．请求出园子里总共有多少水洼？（＊表示八连通，Ｗ表示积水）

＊＊＊

＊ｗ＊

＊＊＊

代码：(来自＜挑战程序设计竞赛＞ｐ３３)

void solve()
    {
        int res = 0;
        int i = 0;
        int j = 0;

        for (i = 0; i < N; i++)
        {
            for (j = 0; j < M; j++)
            {
                if (field[i][j] == 'w')
                {
                    dfs(i, j);
                    res++;
                }
            }
        }

        printf("有%d个水洼!\n", res);
    }

    void dfs(int x, int y)
    {
        int dx = 0;
        int dy = 0;
        int nx = 0;
        int ny = 0;

        field[x][y] = '.';

        for (dx = -1; dx < 2; dx++)
        {
            for (dy = -1; dy < 2; dy++)
            {
                nx = x + dx;
                ny = y + dy;

                if ((nx >= 0) && (nx < N) && (ny >= 0) && (ny < M)
                        &&(field[nx][ny] == 'w'))
                {
                    dfs(nx, ny);
                }
            }
        }
    }