dfs深度优先搜索

可以使用DFS的抽象场景：

1. 树和图的遍历。
2. 解决迷宫、棋盘等问题，比如寻找最短路径、是否存在路径等。
3. 解决连通性问题，比如求连通块的个数、检测一个无向图是否为一棵树等。
4. 深度限制搜索，比如生成所有长度为m的字符串、组合等。
5. 用于寻找隐式图或状态空间搜索，比如经典的八数码等。

使用DFS时需要注意的事项：

1. 防止重复访问。在搜索过程中，需要使用visited数组等方式来确保每个节点被访问一次，避免重复访问。
2. 防止死循环。需要避免重复访问同一个节点，否则可能会出现死循环的情况。
3. 选择好邻居节点。在DFS搜索过程中，需要选择好的邻居节点来递归进行搜索，以提高搜索效率。
4. 理清搜索过程。需要将搜索过程中的状态变化、递归调用等步骤清楚地理解清楚，以便正确地实现算法。

DFS算法步骤：

1. 判断当前节点是否符合条件，如是否已经访问过、是否在矩阵范围内、是否匹配需要找的单词、是否为目标节点等。
2. 如果当前节点符合条件，进行相应的状态变化，然后递归搜索邻居节点。
3. 在递归搜索邻居节点时，需要注意防止死循环和重复访问的情况。
4. 如果找到了目标节点或者匹配成功，返回相应的结果。
5. 如果搜索结束仍然没有找到目标节点或者匹配失败，返回相应的结果。

// DFS算法，全称为深度优先搜索，也称为深搜。
// 它是一种通过搜索所有可能的分支来实现的图形遍历算法，基于树或图的数据结构。
// 在DFS搜索过程中，访问到每个节点后，首先将该节点标记为已访问过，然后递归访问该节点的所有未访问过的邻居。

// dfs算法模型--走迷宫
// 在一个矩阵形式的迷宫中，DFS算法可以用来寻找从起始点到终点的路径。
// 在搜索过程中，每次只从当前节点的未访问过的邻居中选择一条路径继续进行搜索，
// 如果到达了终点则返回成功，否则将回溯到上一个节点进行新的搜索。

#include <stdio.h>

#define ROWS 5
#define COLS 5

int maze[ROWS][COLS] = {
    {0, 0, 0, 0, 0},
    {0, 1, 1, 0, 0},
    {0, 1, 0, 0, 0},
    {0, 0, 1, 1, 0},
    {0, 0, 0, 0, 0}
};

// 使用了一个visited数组来记录每个节点的访问状态，
// 如果一个节点已经被访问过，则将visited数组中相应位置的值置为1，避免出现重复访问的情况。
int visited[ROWS][COLS] = {0};

int dfs(int x, int y)
{
    // 如果在访问一个节点时，发现该节点不符合求解条件（比如在外部边缘，迷宫中存在障碍物，节点已经访问过），则直接返回 0。
    if (x < 0 || y < 0 || x >= ROWS || y >= COLS || maze[x][y] == 1 || visited[x][y] == 1) {
        return 0;
    }
    // 标记节点已经访问过
    visited[x][y] = 1;
    // 标记处查找路径中的访问节点
    printf("%d %d\n", x, y);

    // 如果到达目的节点，则返回1，退出递归搜索
    if (x == 4 && y == 4) {
        return 1;
    }
    // 否则尝试向上下左右4个方向遍历下一个位置
    if (dfs(x+1, y) || dfs(x, y+1) || dfs(x-1, y) || dfs(x, y-1)) {
        return 1;
    }
    visited[x][y] = 0;
    return 0;
}

int main()
{
    dfs(1, 0);
    return 0;
}

// dfs 2. 棋盘游戏
// 在一些棋盘游戏中，DFS算法可以用来查找获得胜利需要的最短步数。
// 在搜索过程中，每次只从当前节点的未访问过的邻居中选择一条路径，
// 然后递归访问下一个节点，直到到达目标位置，然后逆行回溯，更新步数。
// 请使用c语言递归算法实现以上需求，并对编写的实例代码进行详细讲解

// 以下是基于递归实现的C语言代码实例：
// 在这个代码实例中，我们使用递归来实现DFS算法，找出从棋盘左上角到右下角的最短路径。
// 在DFS的实现中，我们使用visited数组来标记已经访问过的节点，避免出现重复访问的情况。
// steps数组用来记录到达每个节点的最短步数。
// 在遍历每个节点的邻居时，只需要递归调用dfs函数，并将步数加1即可。
// 最外层的main函数调用dfs函数来开始在整个棋盘上进行DFS搜索。只要到达终点（右下角），则直接返回。
// 在回溯时，将visited数组中相应位置的值置为0，以便下一次访问。
// 最后，输出steps[ROWS-1][COLS-1]，即终点的最短步数。本例算法的时间复杂度是O(n^2)，其中n指的是棋盘的边长。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define ROWS 5
#define COLS 5

int board[ROWS][COLS] = {
    {0, 0, 0, 0, 0},
    {0, 1, 0, 1, 0},
    {0, 1, 0, 0, 0},
    {0, 1, 1, 1, 0},
    {0, 0, 0, 0, 0}
};

int visited[ROWS][COLS] = {0};
int steps[ROWS][COLS] = {0};

void dfs(int i, int j, int step)
{
    if (i < 0 || j < 0 || i >= ROWS || j >= COLS || board[i][j] == 1 || visited[i][j] == 1) {
        return;
    }
    visited[i][j] = 1;
    steps[i][j] = step;
    if (i == ROWS - 1 && j == COLS - 1) {
        return;
    }
    dfs(i+1, j, step+1);
    dfs(i, j+1, step+1);
    dfs(i-1, j, step+1);
    dfs(i, j-1, step+1);
    visited[i][j] = 0;  // 回溯，释放当前节点
}

int main()
{
    dfs(0, 0, 0);
    printf("%d\n", steps[ROWS-1][COLS-1]);
    return 0;
}

// dfs 词语搜索
// 在一个由大量单词组成的矩阵中，DFS算法可以用来查找指定的单词。
// 在搜索过程中，每次只从当前位置的未访问过的邻居中选择一个字符，
// 继续递归访问下一个位置，直到所有的字符都被匹配到，或者匹配失败后回溯。
// 请使用c语言dfs算法模型编写实例代码实现以上需求，并对代码进行详细讲解

// 以下是基于DFS算法的C语言代码实例：
// 在这个代码实例中，我们使用DFS算法来在一个字符矩阵中查找指定的单词是否存在。
// 在DFS的实现中，我们使用visited数组来记录每个节点的访问状态，
// 如果一个节点已经被访问过，则将visited数组中相应位置的值置为1，避免出现重复访问的情况。
// 如果在访问一个节点时，发现该节点不符合匹配条件
//（比如和需要匹配的字符不相等、已经访问过、不在矩阵范围内等），则直接返回0。
// 如果匹配到了最后一个字符，则返回1，表示匹配成功。
// 否则，对当前位置的四个邻居递归调用dfs函数，尝试匹配下一个字符。
// 在遍历完一个节点的所有未访问的邻居之后，将visited数组中相应位置的值置为0，逆行回溯。
// 最外层的exist函数用来遍历整个矩阵，针对每一个位置都尝试匹配指定的单词，只要有一个匹配成功，立即返回1。
// 如果遍历完整个矩阵，仍然没有找到匹配的单词，返回0。


#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define ROWS 4
#define COLS 4

char board[ROWS][COLS] = {
    {'A', 'B', 'C', 'E'},
    {'S', 'F', 'C', 'S'},
    {'A', 'D', 'E', 'E'},
    {'F', 'A', 'T', 'P'}
};

int visited[ROWS][COLS] = {0};

int dfs(char* word, int index, int i, int j)
{
    if (i < 0 || j < 0 || i >= ROWS || j >= COLS || board[i][j] != word[index] || visited[i][j] == 1) {
        return 0;
    }
    visited[i][j] = 1;
    if (index == strlen(word) - 1) {
        return 1;
    }
    int step1 = dfs(word, index+1, i+1, j);
    int step2 = dfs(word, index+1, i, j+1);
    int step3 = dfs(word, index+1, i-1, j);
    int step4 = dfs(word, index+1, i, j-1);
    visited[i][j] = 0;
    return step1 || step2 || step3 || step4;
}

int exist(char* word)
{
    for (int i = 0; i < ROWS; i++) {
        for (int j = 0; j < COLS; j++) {
            if (dfs(word, 0, i, j)) {
                return 1;
            }
        }
    }
    return 0;
}

int main()
{
    char* word1 = "ABCCED";
    char* word2 = "SEE";
    char* word3 = "ABCB";
    printf("%d\n", exist(word1));  // 1
    printf("%d\n", exist(word2));  // 1
    printf("%d\n", exist(word3));  // 0
    return 0;
}