【重点】【DFS+回溯】剑指offer——面试题66：矩阵中的路径（回溯法）

Allenlzcoder

已于 2025-05-15 01:35:32 修改

阅读量480

点赞数

分类专栏： c/c++ 剑指offer题目笔记文章标签：剑指offer 矩阵中的路径 malloc()/free() new/delete DFS

于 2018-04-06 16:50:26 首次发布

本文链接：https://blog.csdn.net/Allenlzcoder/article/details/79834771

版权

剑指offer题目笔记同时被 2 个专栏收录

80 篇文章

订阅专栏

c/c++

38 篇文章

订阅专栏

本文探讨了DFS+回溯算法解决字符网格中查找目标字符串的问题，并提供了两种实现方案。第一种实现部分AC，存在超时情况；第二种通过优化递归调用方式，有效避免了超时问题。同时，文章还总结了C/C++中malloc/free与new/delete的区别，以及memset函数的使用。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

力扣

1.DFS + 回溯

典型回溯题目，深刻理解！！！

Python

class Solution:
    def wordPuzzle(self, grid: List[List[str]], target: str) -> bool:
        target_array = list(target)
        m, n = len(grid), len(grid[0])
        for i in range(m):
            for j in range(n):
                if grid[i][j] == target_array[0]:
                    visited = [[0]* n for _ in range(m)]
                    res = self.dfs(grid, target_array, 0, i, j, m, n, visited)
                    if res:
                        return res
        return False

    def dfs(self, grid, target_array, index, i, j, m, n, visited):
        if i < 0 or i >= m or j < 0 or j >= n or visited[i][j] or grid[i][j] != target_array[index]:
            return False
        if grid[i][j] == target_array[index] and index == len(target_array) - 1:
            return True
        visited[i][j] = 1
        res = (self.dfs(grid, target_array, index+1, i-1, j, m, n, visited) 
                or self.dfs(grid, target_array, index+1, i+1, j, m, n, visited)
                or self.dfs(grid, target_array, index+1, i, j-1, m, n, visited)
                or self.dfs(grid, target_array, index+1, i, j+1, m, n, visited))
        visited[i][j] = 0 # 回溯重要操作: 还原现场
        return res

Java

第1版部分ac，有的case会超时！！！

class Solution {
    public boolean wordPuzzle(char[][] grid, String target) {
        if (target.length() == 0) {
            return true;
        } else if (grid.length == 0 || grid[0].length == 0) {
            return false;
        }
        int[][] used = new int[grid.length][grid[0].length];
        char[] targetArray = target.toCharArray();
        for (int i = 0; i < grid.length; ++i) {
            for (int j = 0; j < grid[i].length; ++j) {
                if (grid[i][j] == targetArray[0]) {
                    boolean res = dfs(grid, targetArray, used, i, j, 0);
                    if (res) {
                        return res;
                    }
                }
            }
        }
        return false;
    }

    public boolean dfs(char[][] grid, char[] targetArray, int[][] used, int i, int j, int curIndex) {
        if (i < 0 || i >= grid.length 
                || j < 0 || j >= grid[0].length
                || curIndex >= targetArray.length
                || used[i][j] == 1 
                || grid[i][j] != targetArray[curIndex]) {
            return false;
        }
        if (curIndex == targetArray.length - 1) {
            return true;
        }
        used[i][j] = 1;
        boolean res1 = dfs(grid, targetArray, used, i - 1, j, curIndex + 1);
        boolean res2 = dfs(grid, targetArray, used, i + 1, j, curIndex + 1);
        boolean res3 = dfs(grid, targetArray, used, i, j - 1, curIndex + 1);
        boolean res4 = dfs(grid, targetArray, used, i, j + 1, curIndex + 1);
        used[i][j] = 0;
        
        return res1 || res2 || res3 || res4;
    }
}

// 2.优化1
// 按理说不应该，只是修改下写法，复杂度不变！
class Solution {
    public boolean wordPuzzle(char[][] grid, String target) {
        int[][] used = new int[grid.length][grid[0].length];
        char[] targetArray = target.toCharArray();
        for (int i = 0; i < grid.length; ++i) {
            for (int j = 0; j < grid[i].length; ++j) {
                if (grid[i][j] == targetArray[0]) {
                    if (dfs(grid, targetArray, used, i, j, 0)) {
                        return true;
                    }
                }
            }
        }
        return false;
    }

    public boolean dfs(char[][] grid, char[] targetArray, int[][] used, int i, int j, int curIndex) {
        if (i < 0 || i >= grid.length 
                || j < 0 || j >= grid[0].length
                || curIndex >= targetArray.length
                || used[i][j] == 1 
                || grid[i][j] != targetArray[curIndex]) {
            return false;
        }
        if (curIndex == targetArray.length - 1) {
            return true;
        }
        used[i][j] = 1;
        boolean res = dfs(grid, targetArray, used, i - 1, j, curIndex + 1) 
                        || dfs(grid, targetArray, used, i + 1, j, curIndex + 1)
                        || dfs(grid, targetArray, used, i, j - 1, curIndex + 1)
                        || dfs(grid, targetArray, used, i, j + 1, curIndex + 1); // 重点优化这里写法，会避免超时的情况！！！
        used[i][j] = 0;
        
        return res;
    }
}

##Solution:1
典型的回溯算法及代码
此题是回溯法的典型例题，思路以及代码均是书中所讲。要具体实现很有参考价值，借鉴之！
现在把书中代码贴在下面，并对其中用到的一些既熟悉又陌生的语法知识进行总结。

class Solution {
public:
    bool hasPath(char* matrix, int rows, int cols, char* str) { 
        if(matrix == NULL || str == NULL || 
           strlen(matrix) < strlen(str) || 
           rows * cols < 1) 
            return false;
        bool *visited = new bool[rows * cols];
        bool result = false; //new和delete的用法要总结下
        int str_pos = 0;
        memset(visited, 0, rows * cols);  //memset的用法要再总结下
        for(int row = 0; row < rows; row++) {
            for(int col = 0; col < cols; col++) {
                result = IncludePath(matrix, rows, cols, 
                                     str, row, col, 
                                     str_pos, visited);
                if(result)
                    return result;
            }
        }
        delete []visited;
        return false;
    }
    
    //str_pos：表示正在处理str中的第str_pos个字符
    bool IncludePath(char* matrix, int rows, 
                     int cols, char* str, 
                     int row, int col, int &str_pos, 
                     bool* visited) {
        if(str[str_pos] == '\0')
            return true;
        
        bool res = false;
        if(row >= 0 && row < rows && col >= 0 && col <cols
          && matrix[row * cols + col] == str[str_pos] 
          && !visited[row * cols + col]) {
            str_pos++;
            visited[row * cols + col] = true;
            res = IncludePath(matrix, rows, cols, 
                              str, row - 1, col, 
                              str_pos, visited)
                || IncludePath(matrix, rows, cols, 
                               str, row + 1, col, 
                               str_pos, visited)
                || IncludePath(matrix, rows, cols, 
                               str, row, col - 1, 
                               str_pos, visited)
                || IncludePath(matrix, rows, cols, 
                               str, row, col + 1, 
                               str_pos, visited);
            if(res == false) {
                str_pos--;
                visited[row * cols + col] = false;
            }
        }
        return res;
    }
};

##2 C/C++语法知识总结
###2.1 malloc()/free()和new/delete
参考网址：[1]https://blog.csdn.net/hackbuteer1/article/details/6789164
[2]：https://www.cnblogs.com/litao-tech/p/4318424.html
####2.1.1 malloc()/free()和new/delete之相同点
都可用于申请动态内存和释放内存
####2.1.2 malloc()/free()和new/delete之不同点
(1) new/delete是C++的操作符，而malloc()/free()是C中的标准库函数。
(2) new做两件事，一是分配内存，二是调用类的构造函数；同样，delete会调用类的析构函数和释放内存。而malloc()和free()只是分配和释放内存。
(3) 函数malloc()的原型如下：
void * malloc(size_t size);
用malloc()申请一块长度为length的整数类型的内存，程序如下：
int *p = (int *) malloc(sizeof(int) * length);
我们应当把注意力集中在两个要素上：“类型转换”和“sizeof”。
note1：malloc()返回值的类型是void *，所以在调用malloc 时要显式地进行类型转换，将void * 转换成所需要的指针类型。
note2：malloc()函数本身并不识别要申请的内存是什么类型，它只关心内存的总字节数。
函数free 的原型如下：
void free( void * memblock );
为什么free 函数不象malloc()函数那样复杂呢？这是因为指针p 的类型以及它所指的内存的容量事先都是知道的，语句free§能正确地释放内存。如果p 是NULL 指针，那么free()对p无论操作多少次都不会出问题。如果p 不是NULL 指针，那么free 对p连续操作两次就会导致程序运行错误。
(4) new/delete 的使用要点：
运算符new 使用起来要比函数malloc()简单得多，例如：
int *p1 = (int *)malloc(sizeof(int) * length);
int *p2 = new int[length];
这是因为new 内置了sizeof、类型转换和类型安全检查功能。对于非内部数据类型的对象而言，new 在创建动态对象的同时完成了初始化工作。如果对象有多个构造函数，那么new 的语句也可以有多种形式。
如果用new 创建对象数组，那么只能使用对象的无参数构造函数。例如
Obj *objects = new Obj[100]; // 创建100 个动态对象
不能写成
Obj *objects = new Obj[100](1); // 创建100 个动态对象的同时赋初值1
在用delete 释放对象数组时，留意不要丢了符号‘[]’。例如
delete []objects; // 正确的用法
delete objects; // 错误的用法
后者相当于delete objects[0]，漏掉了另外99 个对象。

        1、new自动计算需要分配的空间，而malloc需要手工计算字节数
        2、new是类型安全的，而malloc不是，比如：
                 int* p = new float[2]; // 编译时指出错误
                 int* p = malloc(2*sizeof(float)); // 编译时无法指出错误
           new operator 由两步构成，分别是 operator new 和 construct
        3、operator new对应于malloc，但operator new可以重载，可以自定义内存分配策略，
           甚至不做内存分配，甚至分配到非内存设备上。而malloc无能为力
        4、new将调用constructor，而malloc不能；delete将调用destructor，而free不能。
        5、malloc/free要库文件支持，new/delete则不要。

###2.2 字符串函数之memset()
参考链接：https://www.cnblogs.com/cyyljw/p/6855152.html
void *memset(void *s,int c,size_t n)
总的作用：将已开辟内存空间 s 的首 n 个字节的值设为值 c。
memset() 函数常用于内存空间初始化。如：
char str[100];
memset(str,0,100);
memset()的深刻内涵：用来对一段内存空间全部设置为某个字符，一般用在对定义的字符串进行初始化为‘ ’或‘/0’；例:char a[100];memset(a, ‘/0’, sizeof(a));