剑指offer第二版-12.矩阵中的路径（回溯法）

本系列导航：剑指offer（第二版）java实现导航帖

面试题12：矩阵中的路径

题目要求：
设计一个函数，用来判断一个矩阵中是否存在一条包含某字符串的路径。
（1）起点随意；（2）路径的移动只能是上下左右；（3）访问过的位置不能再访问。以下图矩阵为例，包含“bfce”，但是不包含“abfb”。

a      b      t      g
c      f      c      s
j      d      e      h

解题思路：
本题考察回溯法。
回溯法适合解决由多个步骤组成的问题，且每个步骤都有多个选项。当在某一步选择了其中一个选项，就进入下一步，然后面临新的选项。如果当前的选项已经确定没有正确答案，就回溯到上一步，在上一步选择另一选项，重复进行。回溯法的求解过程一般都可以用树状结构表示出来。实现代码很适合用递归完成。
至于本题，需要明确递归的约束条件，回溯的终止条件，标记矩阵的标记与清除时机。具体可以看下述代码，关键部分已经做了注释。

package chapter2;

/**
 * Created by ryder on 2017/7/2.
 * 矩阵中的路径
 */
public class P89_StringPathInMatrix {
    //回溯法解决
    public static boolean hasPath(char[][] data,String str){
        if(data==null || data.length==0 || str==null || str.length()==0)
            return false;
        int rowLen = data.length;
        int colLen = data[0].length;
        boolean[][] visitFlag = new boolean[rowLen][colLen];
        for(int row=0;row<rowLen;row++){
            for(int col=0;col<colLen;col++){
                visitFlag[row][col] = false;
            }
        }
        for(int row=0;row<rowLen;row++){
            for(int col=0;col<colLen;col++){
                if(hasPathCore(data,row,col,visitFlag,str,0))
                    return true;
            }
        }
        return false;
    }
    public static boolean hasPathCore(char[][] data,int rowIndex,int colIndex,
                                    boolean[][] visitFlag,String str,int strIndex){
        //结束条件
        if(strIndex>=str.length()) return true;
        if(rowIndex<0 || colIndex<0 || rowIndex>=data.length || colIndex>=data[0].length) 
            return false;

        //递归
        if(!visitFlag[rowIndex][colIndex]&&data[rowIndex][colIndex]==str.charAt(strIndex)){
            //如果未被访问，且匹配字符串，标记当前位置为已访问，分上下左右四个位置递归求解
            visitFlag[rowIndex][colIndex] = true;
            boolean result =  
                    hasPathCore(data,rowIndex+1,colIndex,visitFlag,str,strIndex+1) ||
                    hasPathCore(data,rowIndex-1,colIndex,visitFlag,str,strIndex+1) ||
                    hasPathCore(data,rowIndex,colIndex+1,visitFlag,str,strIndex+1) ||
                    hasPathCore(data,rowIndex,colIndex-1,visitFlag,str,strIndex+1);
            //已经求的结果，无需修改标记了
            if(result)
                return true;
            //当前递归的路线求解失败，要把这条线路上的标记清除掉
            //因为其他起点的路径依旧可以访问本路径上的节点。
            else{
                visitFlag[rowIndex][colIndex] = false;
                return false;
            }
        }
            else
            return false;
    }
    public static void main(String[] args){
        char[][] data = {
                {'a','b','t','g'},
                {'c','f','c','s'},
                {'j','d','e','h'}};
        System.out.println(hasPath(data,"bfce")); //true
        System.out.println(hasPath(data,"abfb")); //false,访问过的位置不能再访问
    }
}

运行结果

true
false