剑指offer----C语言版----第八天-创新互联

目录

1. 矩阵中的路径

1.1 题目描述

1.2 基础知识

1.3 思路分析

1.4 小试牛刀

原题链接：

剑指 Offer 12. 矩阵中的路径 - 力扣（LeetCode）https://leetcode.cn/problems/ju-zhen-zhong-de-lu-jing-lcof/submissions/

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

回溯法可以看成蛮力法的升级，他从解决问题每一步的所有可能选项里系统地选择出一个可行的解决方案。回溯法非常适合由多个步骤组成的问题，并且每个步骤都有多个选项。当我们在某一步选择了其中一个选项时，就进入下一步，然后又面临新的选择。我们就这样重复选择直到达到最终的状态。

用回溯法解决问题的所有选项可以形象地用树状结构表示。在某一步可能有n个可能的选项，那么该步骤可以看成是树状结构中的一个节点，每个选项看成树中节点的连接线，经过这些连接线到达该节点的n个子节点。树的叶节点对应着最终的状态。如果在叶节点的状态满足题目的约束条件，那我们就找到了一个可行的解决方案。

如果不满足条件就回溯到上一个节点，再尝试其他的选项。如果所有节点的所有选项都已经尝试过依然不能达到满足约束条件的终结状态，则该问题无解。

通常回溯算法适合用递归实现。当我们到达某一个节点时，尝试所有可能的选项并在满足条件的前提下递归地抵达下一个节点。

有了以上的基础知识，我们以一个具体的例子对该题进行分析。

以输入矩阵   A    B   C   E

S    F   C   S

A    D   E    F    ，输入字符串 "BFCE"为例。

首先我们需要遍历输入的矩阵，把每一个下标的位置都作为一次递归的起点，尝试往下递归。这时在递归函数的内部我们就需要对进入递归函数的下标做合法性判断，并且与输入字符串的第一个字符进行比较，若与字符串的第一个字符相等，我们就找到了可以继续往下递归的位置啦。为此在递归函数的参数上需要一个下标变量，能够在递归的过程中，逐步遍历到输入字符串的每一个字符。（找到解题路径的依据就是匹配到输入字符串的每一个字符嘛）

对于上述例子，遍历输入字符串的下标变量不妨设为index，初始时index为0，对应输入的字符B，当我们尝试递归B这个位置时，他与index指向的字符相等，我们就让下一层递归时index的值加1指向下一个查找的字符，即尝试去找到 F这个字符。

另外对于一个位置的递归，根据题目要求走过的位置是不能够再走的，因此递归时，需要对当前递归位置的矩阵中的字符进行记录后，对其进行修改，比如修改为 '#'，以此来防止出现往回走的情况。同时无论找没找到解题的路线在回溯的过程中都需要将修改过的字符改回来（通过保存的记录来修改），不然就无法进行矩阵中下一个位置最开始的查找啦（遍历矩阵从矩阵中的每一个位置尝试递归查找嘛）。

根据最开始的基础知识，我们假设对于每一个位置的查找是按照上，下，左，右的顺序，画出一个树状图来分析。分析例子还是：

以输入矩阵   A    B   C   E

S    F   C   S

A    D   E    F    ，输入字符串 "BFCE"为例。

在对上下左右的方向查找index+1指向的字符时，只要我们找到一条解题的路即可，假设有多条解题路线，我们改变上下左右这四个方向的顺序，查找到的结果可能是不同的。

当index指向的字符正好为strlen(输入的字符串) - 1 时，就找到了解题的路径，注意对递归进来的坐标进行合法性判断的语句在该语句之前确保了已经找到了输入字符串的最后一个字符。

我们对上下左右方向的递归采取  | |  的逻辑运算返回最终的结果，只要一个方向向下的递归找到了解题的路径，就能够逐层返回true，完成解题。

bool recurison(char** board, int boardSize, int* boardColSize, char* word, int i, int j, int index)
{
    //对递归进来的坐标进行合法性判断，并且对该位置的字符与index指向的字符判断，不相等就结束当            
      前层的递归
    if(i<0||i>=boardSize||j<0||j>=*boardColSize|| board[i][j] != word[index])
    {
        return false;
    }
    //如果执行此条语句证明找到了解题的路线
    if(index == strlen(word) - 1)
    {
        return true;
    }
    //记录递归当前层位置的字符，方便后续回溯时将被修改过的字符换回来
    char tmp = board[i][j];
    //走过的位置进行修改，不允许再次递归
    board[i][j] = '#';
    //对该位置的上下左右方向的字符进行查找判断，index加一表示将要查找的字符
    bool ret = recurison(board, boardSize, boardColSize,word, i - 1,j,index+1) || 
               recurison(board, boardSize, boardColSize,word, i + 1,j,index+1) ||
               recurison(board, boardSize, boardColSize,word, i,j + 1,index+1) ||
               recurison(board, boardSize, boardColSize,word, i,j - 1,index+1);
    //回溯时改回来被修改的字符
    board[i][j] = tmp;
    //返回当前递归层的结果
    return ret;
}

bool exist(char** board, int boardSize, int* boardColSize, char* word){
    int i = 0;
    int j = 0;
    for(i=0;i