题目

• 给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
• 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

题目

示例

• 示例1

输入：board

[
    ["A","B","C","E"],
    ["S","F","C","S"],
    ["A","D","E","E"]
]

word = "ABCCED"

输出：true

• 示例2

输入：board

[
    ["a","b"],
    ["c","d"]
]

word = "abcd"

输出：false

代码

解法： DFS

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        for(int i = 0; i < board.size(); i++)
            for(int j = 0; j < board[0].size(); j++)
                if(dfs(board,word,0,i,j))   return true;
        return false;
    }
    bool dfs(vector<vector<char>>& arr,string& str,int u,int x,int y){
        if(arr[x][y] != str[u]) return false;
        if(u == str.size()-1)   return true;

        int t = arr[x][y];
        arr[x][y] = '*';

        // 开方向数组
        int dx[4] = {-1,0,1,0},dy[4] = {0,1,0,-1};
        for(int i = 0; i < 4; i++){
            int a = x + dx[i],b = y + dy[i];
            if(a >= 0 && a < arr.size() && b >= 0 && b < arr[0].size() && dfs(arr,str,u+1,a,b))    return true;
        }
        arr[x][y] = t;
        return false;
    }
};

代码分析：1、已经是第二次见这种题了，路径搜索很常见，这题也是很经典。参照文章：

if(arr[x][y] != str[u]) return false;

说明 arr[x][y] 不能作为路径起点，直接返回 false。

if (u == str.size() - 1) return true;

截止条件，从 0 开始计数，所以 u == str.size() - 1时，就是找到了一条有效的路径

for(int i = 0; i < 4; i++){
    int a = x + dx[i],b = y + dy[i];
    if(a >= 0 && a < arr.size() && b >= 0 && b < arr[0].size() && dfs(arr,str,u+1,a,b))
        return true;
}

接着 for 循环向 上右下左 四个方向依次遍历(跟随方向数组)

if (dfs(arr, str, u + 1, a, b)) return true;

如果找得到，会依次返回 true

arr[x][y] = t;   // 恢复

对于矩阵中每一个坐标的搜索，如果找到了就返回true了，如果没找到，需要恢复该坐标的原值。

题目：矩阵中的路径