LeetCode 矩阵中的路径

题目描述

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

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

例如，在下面的 3×4 的矩阵中包含单词 “ABCCED”（单词中的字母已标出）。

示例：

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true

输入：board = [["a","b"],["c","d"]], word = "abcd"
输出：false

解题想法

这道题一开始想到的是使用BFS，但是细想发现BFS好像很难处理回溯的问题，应该采用DFS。然后，就是递归的痛了，也借这道题学习一下DFS的写法吧。

**DFS：**即是暴力遍历矩阵的所有元素，来搜索一条可行的路径，通过递归，可以在一条路径中搜索到底，最后回溯到之前已经匹配的节点。

**剪枝：**在DFS过程中如果当前的矩阵字符与字符串字符不等，可以直接回溯。或者路径已经访问过，可以直接跳过。

DFS解析

1、递归终止条件：

（a）、返回true，当匹配到字符串的最后一个字符时，可以直接返回true（至于为什么可以这样返回，参看代码注释）

（b）、返回false，如果矩阵的索引越界，当前矩阵的字符和字符串的字符不匹配，当前元素已经访问过了直接返回false

2、递归过程

（a）、选定当前元素，将当前元素标记为空字符，表明当前元素已经访问过，防止走回头路。

（b）、搜索下一个元素，向四个方向分别匹配字符，如果有一个方向可以匹配就继续递归这个方向的DFS算法，并返回true，否则返回false

（c）、还原当前元素，需要在DFS算法退出之前，将空字符还原为原来的字符，用于回溯时重新寻找路径，否则回溯将找不到正确路径。

代码

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        rows = board.size();
        cols = board[0].size();
        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                if (dfs(board, word, i, j, 0)) return true;
            }
        }
        return false;
    }
private:
    int rows, cols;
    // k为单词索引
    bool dfs(vector<vector<char>> &board, string word, int i, int j, int k) {
        // 如果越界或者字符不相等，就停止递归
        if (i >= rows || i < 0 || j >= cols || j < 0 || board[i][j] != word[k]) 
            return false;
        // 当进入这个判断条件时，会先判断是否相等，因此只要走到最后一个字符就可以返回true
        if (k == word.size() - 1) return true;
        // 将访问过的字符设为一个特殊字符，防止走回头路
        board[i][j] = '\0';
        array<int, 4> dx{0, 1, 0, -1};
        array<int, 4> dy{1, 0, -1, 0};
        for (int idx = 0; idx < 4; ++idx) {
            if (dfs(board, word, i + dx[idx], j + dy[idx], k + 1)) {
                return true;
            }
        }
        // 在退出dfs之前要恢复board，否则回溯将无法找到正确路径
        board[i][j] = word[k]; 
        return false;
    }
};