本系列導(dǎo)航：劍指offer（第二版）java實(shí)現(xiàn)導(dǎo)航帖

面試題12：矩陣中的路徑

題目要求：
設(shè)計(jì)一個(gè)函數(shù)，用來(lái)判斷一個(gè)矩陣中是否存在一條包含某字符串的路徑。
（1）起點(diǎn)隨意；（2）路徑的移動(dòng)只能是上下左右塞茅；（3）訪(fǎng)問(wèn)過(guò)的位置不能再訪(fǎng)問(wèn)。以下圖矩陣為例季率，包含“bfce”野瘦，但是不包含“abfb”。

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

解題思路：
本題考察回溯法飒泻。
回溯法適合解決由多個(gè)步驟組成的問(wèn)題缅刽，且每個(gè)步驟都有多個(gè)選項(xiàng)啊掏。當(dāng)在某一步選擇了其中一個(gè)選項(xiàng)蠢络，就進(jìn)入下一步衰猛，然后面臨新的選項(xiàng)。如果當(dāng)前的選項(xiàng)已經(jīng)確定沒(méi)有正確答案刹孔，就回溯到上一步啡省，在上一步選擇另一選項(xiàng)，重復(fù)進(jìn)行髓霞∝远茫回溯法的求解過(guò)程一般都可以用樹(shù)狀結(jié)構(gòu)表示出來(lái)。實(shí)現(xiàn)代碼很適合用遞歸完成方库。
至于本題结序，需要明確遞歸的約束條件，回溯的終止條件纵潦，標(biāo)記矩陣的標(biāo)記與清除時(shí)機(jī)徐鹤。具體可以看下述代碼，關(guān)鍵部分已經(jīng)做了注釋邀层。

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){
        //結(jié)束條件
        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)){
            //如果未被訪(fǎng)問(wèn)返敬，且匹配字符串，標(biāo)記當(dāng)前位置為已訪(fǎng)問(wèn)寥院，分上下左右四個(gè)位置遞歸求解
            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);
            //已經(jīng)求的結(jié)果劲赠，無(wú)需修改標(biāo)記了
            if(result)
                return true;
            //當(dāng)前遞歸的路線(xiàn)求解失敗，要把這條線(xiàn)路上的標(biāo)記清除掉
            //因?yàn)槠渌瘘c(diǎn)的路徑依舊可以訪(fǎng)問(wèn)本路徑上的節(jié)點(diǎn)秸谢。
            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,訪(fǎng)問(wèn)過(guò)的位置不能再訪(fǎng)問(wèn)
    }
}

運(yùn)行結(jié)果

true
false