矩阵中的路径(DFS暴搜)

题目链接

解题思路

• 使用dfs枚举所有的可能路径，如果存在一条路径是输入的字符串就返回true，否则返回false.

1. 寻找搜索的起始点（与st[0]相等的字母）

for(int i = 0; i < matrix.size(); i ++)
    for(int j = 0; j < matrix.size(); j ++)
        if(dfs(matrix, str, i, j))

2. 拓展相邻节点

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, -1, 0, 1};  // 用for循环遍历一遍

3. 设置正确的退出点，不符合条件点（坐标越界，字符串长度越界）
4. 退出后，要恢复现场。

解题遇到的问题及解决思路

• 如何标记一个点已经被走过，用于进行回溯 ？

matrix[x][y] = '*'; // 这里直接标记矩阵的点为'*',省去了另外开辟的一个标记数组的空间

• 为什么标记为'*'的点之后要恢复现场 ？

  因为每个点一旦被遍历，就会被标记成'*'，那么每个点就最多只会被遍历一次。但同一个点是有可能出现在多条路径中的，所以不恢复现场的话就会漏掉很多情况。

参考代码

class Solution {
public:
    bool hasPath(vector<vector<char>>& matrix, string &str) {
        for (int i = 0; i < matrix.size(); i ++ )
            for (int j = 0; j < matrix[i].size(); j ++ )
                if (dfs(matrix, str, 0, i, j)) return true;
        return false;
    }
    
    bool dfs(vector<vector<char>>& matrix, string &str, int u, int x, int y){
        if (matrix[x][y] != str[u]) return false;
        if (u == str.size() - 1) return true;
        int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, -1, 0, 1};
        matrix[x][y] = '*';
        for(int i = 0; i < 4; i ++){
            int a = x + dx[i], b = y + dy[i];
            if(a >= 0 && a < matrix.size() && b >= 0 && b < matrix[a].size())
            {
                if(dfs(matrix, str, u + 1, a, b)) return true;
            }
        }
        matrix[x][y] = str[u];
        return false;
    }
};