矩阵中的路径

ryluo 2020-06-22 23:07:46

请设计一个函数,用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。

路径可以从矩阵中的任意一个格子开始,每一步可以在矩阵中向左,向右,向上,向下移动一个格子。

如果一条路径经过了矩阵中的某一个格子,则之后不能再次进入这个格子。

注意:

样例

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

str="BCCE" , return "true" 

str="ASAE" , return "false"

分析:

  1. 先枚举所有可能的起点
  2. 有了起点之后再枚举所有可能的方向
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[0].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; // 这一步保证了当前位置等于str(u)
        if (str.size() - 1 == u) return true; // 如果字符串的长度与经过的路径相等就返回true

        char t = matrix[x][y];  // 为了防止相同字符被多次经过,将已经访问过的字符设置成特殊字符
        matrix[x][y] = '*';

        // 遍历四个方向
        int dx[4] = {0, 0, -1, 1}, dy[4] = {-1, 1, 0, 0};
        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[0].size()) // 判断边界
                if (dfs(matrix, str, u + 1, a, b)) return true; // 递归查找
        }

        matrix[x][y] = t;
        return false;
    }   
};