矩阵中的路径----深度优先遍历-白红宇

矩阵中的路径----深度优先遍历

阅读量：3623 次

发布时间：2019-05-21

本文共 2134 字，大约阅读时间需要 7 分钟。

题目：

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

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

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

注意：	输入的路径不为空；	所有出现的字符均为大写英文字母；样例matrix=[  ["A","B","C","E"],  ["S","F","C","S"],  ["A","D","E","E"]]结果：str="BCCE" , return "true" str="ASAE" , return "false"

思路分析

问题分析：

二维矩阵中找一条连续的字符串，且每个字符不能重复使用。

可以上下左右四个方向遍历。

思路：

1、先遍历二维数组，找到字符串首字母相同的字符作为起点；

2、从该起点依次从上下左右四个方向移动不断地组成字符串与当前字符串进行匹配，如果匹配成功，则返回true，否则，继续。

3、每次从当前点往各个方向移动之前，先将当前的字符设置为‘\0’，这样保证了当前点不会被重复计算

4、四个方向返回之后，将当前值修改成原来值。

代码

class Solution {
   public:    bool dfs(vector
   
    
     >& matrix, string &str, int idx, int row, int col) {
           vector
     
       tmp = matrix[0];        // 越界直接返回false        if (row < 0 || row >= matrix.size()  || col < 0 || col >= matrix[0].size()) {
               return false;        }        // 当前值与字符串对应的值不匹配，返回false        if (matrix[row][col] != str[idx]) {
               return false;        }        // 如果字符串全部匹配成功，返回true        if (idx == str.length() - 1) {
               return true;        }                char tmpc = matrix[row][col];        // 继续遍历之前将当前值修改为'\0'，防止重复判断        matrix[row][col] = '\0';        // 上下左右四个方向继续搜索。        if(dfs(matrix, str, idx+1, row - 1, col)) {
               return true;        }        if(dfs(matrix, str, idx+1, row + 1, col)) {
               return true;        }        if (dfs(matrix, str, idx+1, row, col - 1)) {
               return true;        }        if (dfs(matrix, str, idx+1, row, col + 1)) {
               return true;        }        // 计算完成后，还原当前值。        matrix[row][col] = tmpc;        return false;    }        bool hasPath(vector
      
       
        >& matrix, string &str) {
           for (int i = 0; i < matrix.size(); i++) {
               for (int j = 0; j < matrix.at(0).size(); j++) {
                   // 找到当前字符串第一个字符相同的位置开始                if (matrix[i][j] == str[0]) {
                       bool ret = dfs(matrix, str, 0, i, j);                    if(ret) {
                           return ret;                    }                }            }        }        return false;    }};