劍指offer-矩陣中的路徑

印度阿三17 2019-02-12

展開全文

請設計一個函數(shù)，用來判斷在一個矩陣中是否存在一條包含某字符串所有字符的路徑。路徑可以從矩陣中的任意一個格子開始，每一步可以在矩陣中向左，向右，向上，向下移動一個格子。如果一條路徑經(jīng)過了矩陣中的某一個格子，則該路徑不能再進入該格子。

例如下面的矩陣包含了一條 bfce 路徑。（因為題目中的矩陣是用一維數(shù)組來表示二維數(shù)組的）

來源：?？途W(wǎng)

分析：回溯算法

這是一個可以用回朔法解決的典型題。首先，在矩陣中任選一個格子作為路徑的起點。如果路徑上的第i個字符不是ch，那么這個格子不可能處在路徑上的

第i個位置。如果路徑上的第i個字符正好是ch，那么往相鄰的格子尋找路徑上的第i 1個字符。除在矩陣邊界上的格子之外，其他格子都有4個相鄰的格子。

重復這個過程直到路徑上的所有字符都在矩陣中找到相應的位置。

　　由于回朔法的遞歸特性，路徑可以被開成一個棧。當在矩陣中定位了路徑中前n個字符的位置之后，在與第n個字符對應的格子的周圍都沒有找到第n 1個

字符，這個時候只要在路徑上回到第n-1個字符，重新定位第n個字符。

　　由于路徑不能重復進入矩陣的格子，還需要定義和字符矩陣大小一樣的布爾值矩陣，用來標識路徑是否已經(jīng)進入每個格子。 當矩陣中坐標為（row,col）的

格子和路徑字符串中相應的字符一樣時，從4個相鄰的格子(row,col-1),(row-1,col),(row,col 1)以及(row 1,col)中去定位路徑字符串中下一個字符

如果4個相鄰的格子都沒有匹配字符串中下一個的字符，表明當前路徑字符串中字符在矩陣中的定位不正確，我們需要回到前一個，然后重新定位。

　　一直重復這個過程，直到路徑字符串上所有字符都在矩陣中找到合適的位置

鏈接：https://www./questionTerminal/c61c6999eecb4b8f88a98f66b273a3cc
來源：?？途W(wǎng)

核心思路：回溯法
1.先將matrix字符串映射為字符矩陣；
2.從原字符串中找到第一個跟str[0]相等的字符，得到其對應的在矩陣中的位置[r,c]
1）從[r,c]開始按 上、左、右、下的順序搜索；
2）每當搜索到一個節(jié)點，先判斷path是否包括它，包括就說明已經(jīng)經(jīng)過此節(jié)點，不能
再經(jīng)過了；如果不包括，就將其加入path容器
3）直到搜索到str[length - 1]節(jié)點，說明成功找到，標記result為true，標記
isFinished為true,盡快結(jié)束所有的遞歸操作
4）如果某節(jié)點起的 上、左、右、下 都搜索過但還沒找到結(jié)果，說明經(jīng)過此節(jié)點的路
徑都不滿足題意，將其從path中刪除，回溯到上一層繼續(xù)找。
（PS:確實是回溯法，不過代碼有點長，實現(xiàn)的有點繁雜）

public class Solution {
    private final static int[][] dir = {{0,-1},{0,1},{-1,0},{1,0}};
    private int row, col;
    public boolean hasPath(char[] matrix, int rows, int cols, char[] str)
    {    
         if(row==0 || col==0) return false;
        this.row = row;
        this.col = col;
        boolean[][] flag = new boolean[row][col];
        //char[][] a = build(matrix);
        char a[][] = new char[row][col];
        for(int i=0,k=0; i<row; i  ) {
            for(int j=0; j<col; j  ) {
                a[i][j] = matrix[k  ];
            }
        }
        for(int i=0; i<row; i  ) {
            for(int j=0; j<col; j  ) 
                if(dfs(a,str,flag,0,i,j)) 
                    return true;
        }
        return false;
    }
    private boolean dfs(char[][] a,char[] str,boolean[] flag,int pathLen, int r,int c){
        if(pathLen == str.length) return true;
        if(r<0 || r>=row || c<0 || c>=col || a[r][c] != str[pathLen] || flag[r][c])
            return false;
        flag[r][c] = true;
        for(int[] d:dir) {
            if(dfs(a,str,flag,pathLen 1,r d[0],c d[1])) 
                return true;
    }
        flag[r][c]=false;
        return false;
}

鏈接：https://www./questionTerminal/c61c6999eecb4b8f88a98f66b273a3cc
來源：?？途W(wǎng)

    public boolean hasPath(char[] matrix, int rows, int cols, char[] str){
        boolean[] visited = new boolean[matrix.length];
        for (int i = 0; i < rows; i  ) {
            for (int j = 0; j < cols; j  ) {
                if (searchFromHere(matrix,rows,cols,i,j,0,str,visited))
                    return true;
            }
        }
//        System.out.println(Arrays.toString(visited));
        return false;
    }
    public boolean searchFromHere(char[] matrix,int rows,int cols,int r,int c,int index,char[] str,boolean[] visited){
        if (r < 0 || r >= rows || c < 0 || c >= cols || matrix[r * cols   c] != str[index] || visited[r * cols   c])
            return false;
        if (index == str.length - 1)    return true;
        visited[r * cols   c] = true;
        if (searchFromHere(matrix,rows,cols,r - 1,c,index   1,str,visited) ||
                searchFromHere(matrix,rows,cols,r,c -1,index   1,str,visited) ||
                searchFromHere(matrix,rows,cols,r   1,c,index   1,str,visited) ||
                searchFromHere(matrix,rows,cols,r,c   1,index   1,str,visited))
            return true;
        visited[r * cols   c] = false;
        return false;
    }

鏈接：https://www./questionTerminal/c61c6999eecb4b8f88a98f66b273a3cc
來源：牛客網(wǎng)

回溯基本思想： 0.根據(jù)給定數(shù)組，初始化一個標志位數(shù)組，初始化為false，表示未走過，true表示已經(jīng)走過，不能走第二次 1.根據(jù)行數(shù)和列數(shù)，遍歷數(shù)組，先找到一個與str字符串的第一個元素相匹配的矩陣元素，進入judge 2.根據(jù)i和j先確定一維數(shù)組的位置，因為給定的matrix是一個一維數(shù)組 3.確定遞歸終止條件：越界，當前找到的矩陣值不等于數(shù)組對應位置的值，已經(jīng)走過的，這三類情況，都直接false，說明這條路不通 4.若k，就是待判定的字符串str的索引已經(jīng)判斷到了最后一位，此時說明是匹配成功的 5.下面就是本題的精髓，遞歸不斷地尋找周圍四個格子是否符合條件，只要有一個格子符合條件，就繼續(xù)再找這個符合條件的格子的四周是否存在符合條件的格子，直到k到達末尾或者不滿足遞歸條件就停止。 6.走到這一步，說明本次是不成功的，我們要還原一下標志位數(shù)組index處的標志位，進入下一輪的判斷。

鏈接：https://www./questionTerminal/c61c6999eecb4b8f88a98f66b273a3cc
來源：?？途W(wǎng)

public class Solution {
    public boolean hasPath(char[] matrix, int rows, int cols, char[] str)
    {
        //標志位，初始化為false
        boolean[] flag = new boolean[matrix.length];
        for(int i=0;i<rows;i  ){
            for(int j=0;j<cols;j  ){
                 //循環(huán)遍歷二維數(shù)組，找到起點等于str第一個元素的值，再遞歸判斷四周是否有符合條件的----回溯法
                 if(judge(matrix,i,j,rows,cols,flag,str,0)){
                     return true;
                 }
            }
        }
        return false;
    }
     
    //judge(初始矩陣，索引行坐標i，索引縱坐標j，矩陣行數(shù)，矩陣列數(shù)，待判斷的字符串，字符串索引初始為0即先判斷字符串的第一位)
    private boolean judge(char[] matrix,int i,int j,int rows,int cols,boolean[] flag,char[] str,int k){
        //先根據(jù)i和j計算匹配的第一個元素轉(zhuǎn)為一維數(shù)組的位置
        int index = i*cols j;
        //遞歸終止條件
        if(i<0 || j<0 || i>=rows || j>=cols || matrix[index] != str[k] || flag[index] == true)
            return false;
        //若k已經(jīng)到達str末尾了，說明之前的都已經(jīng)匹配成功了，直接返回true即可
        if(k == str.length-1)
            return true;
        //要走的第一個位置置為true，表示已經(jīng)走過了
        flag[index] = true;
         
        //回溯，遞歸尋找，每次找到了就給k加一，找不到，還原
        if(judge(matrix,i-1,j,rows,cols,flag,str,k 1) ||
           judge(matrix,i 1,j,rows,cols,flag,str,k 1) ||
           judge(matrix,i,j-1,rows,cols,flag,str,k 1) ||
           judge(matrix,i,j 1,rows,cols,flag,str,k 1)  )
        {
            return true;
        }
        //走到這，說明這一條路不通，還原，再試其他的路徑
        flag[index] = false;
        return false;
    }