矩阵中的路径

[TOC]

题目描述

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则之后不能再次进入这个格子。例如 a b c e s f c s a d e e 这样的 3 X 4 矩阵中包含一条字符串 ”bcced” 的路径，但是矩阵中不包含 ”abcb” 路径，因为字符串的第一个字符 b 占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。

public class Solution {public boolean hasPath(char[] matrix, int rows, int cols, char[] str){}}

思路

采用回溯法，从矩阵的第一个节点开始搜索，一旦搜索到和字符串的字符相等，那么又从该节点的上，下，左，右节点进行搜索是否和下一个字符相等，如果搜索完上下左右都不相等，那么就回退到上一个字符，重新继续搜索

 public boolean hasPath(char[] matrix, int rows, int cols, char[] str) {if(matrix == null || matrix.length == 0 || str == null || str.length == 0 || rows * cols != matrix.length)
            return false;
        boolean[] isVisited = new boolean[rows * cols];
        int pathLen = 0;
        for(int i = 0; i < rows; i++){for(int j = 0; j < cols; j++){if(hasPathCore(matrix,rows,cols,i,j,str,isVisited,pathLen))
                    return true;
            }

        }
        return false;
    }
    public boolean hasPathCore(char[] matrix,int rows,int cols,int row,int col,char[] str,boolean[] isVisited,int pathLen){
        boolean flag = false;
        int index = row * cols + col;
        if(row >= 0 && row < rows && col >= 0 && col < cols && !isVisited[index] && matrix[index] == str[pathLen]){
            pathLen++;
            isVisited[index] = true;
            if(pathLen==str.length)
                return true ;
            flag = hasPathCore(matrix,rows,cols,row,(col + 1),str,isVisited,pathLen) ||
                   hasPathCore(matrix,rows,cols,row,(col - 1),str,isVisited,pathLen) ||
                   hasPathCore(matrix,rows,cols,row+1,col,str,isVisited,pathLen) ||
                   hasPathCore(matrix,rows,cols,row-1,col,str,isVisited,pathLen) ;
            if(!flag){
                pathLen--;
                isVisited[index] = false;
            }
        }
        return flag;
    }

补充: 回溯法（退一步海阔天空）

什么是回溯法

采用试错的思想，分步去解决问题，在分步解决问题的过程中发现现有的分步答案是错的，那么就放弃或者回退到上一步甚至上几步，然后通过其他分步去继续寻找答案。

回溯法通常用最简单的递归方法来实现，在反复重复上述的步骤后可能出现两种情况：

• 找到一个可能存在的正确的答案
• 在尝试了所有可能的分步方法后宣告该问题没有答案
  在最坏的情况下，回溯法会导致一次复杂度为指数时间的计算。

回溯法的特点

1、按照选优条件深度优先搜索

2、当发现并不是最优或者达不到目标时，退回一步重新搜索

3、能进则进，进不了则换，换不了则退

参考

《剑指 offer 纪念版》

《趣学算法》