免费视频淫片aa毛片_日韩高清在线亚洲专区vr_日韩大片免费观看视频播放_亚洲欧美国产精品完整版

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

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

來源：牛客網(wǎng)

分析：回溯算法 這是一個可以用回朔法解決的典型題。首先，在矩陣中任選一個格子作為路徑的起點。如果路徑上的第i個字符不是ch，那么這個格子不可能處在路徑上的第i個位置。如果路徑上的第i個字符正好是ch，那么往相鄰的格子尋找路徑上的第i 1個字符。除在矩陣邊界上的格子之外，其他格子都有4個相鄰的格子。重復(fù)這個過程直到路徑上的所有字符都在矩陣中找到相應(yīng)的位置。 　　由于回朔法的遞歸特性，路徑可以被開成一個棧。當(dāng)在矩陣中定位了路徑中前n個字符的位置之后，在與第n個字符對應(yīng)的格子的周圍都沒有找到第n 1個字符，這個時候只要在路徑上回到第n-1個字符，重新定位第n個字符。 　　由于路徑不能重復(fù)進入矩陣的格子，還需要定義和字符矩陣大小一樣的布爾值矩陣，用來標(biāo)識路徑是否已經(jīng)進入每個格子。 當(dāng)矩陣中坐標(biāo)為（row,col）的格子和路徑字符串中相應(yīng)的字符一樣時，從4個相鄰的格子(row,col-1),(row-1,col),(row,col 1)以及(row 1,col)中去定位路徑字符串中下一個字符如果4個相鄰的格子都沒有匹配字符串中下一個的字符，表明當(dāng)前路徑字符串中字符在矩陣中的定位不正確，我們需要回到前一個，然后重新定位。 　　一直重復(fù)這個過程，直到路徑字符串上所有字符都在矩陣中找到合適的位置

鏈接：https://www.nowcoder.com/questionTerminal/c61c6999eecb4b8f88a98f66b273a3cc來源：牛客網(wǎng)核心思路：回溯法1.先將matrix字符串映射為字符矩陣；2.從原字符串中找到第一個跟str[0]相等的字符，得到其對應(yīng)的在矩陣中的位置[r,c]1）從[r,c]開始按 上、左、右、下的順序搜索；2）每當(dāng)搜索到一個節(jié)點，先判斷path是否包括它，包括就說明已經(jīng)經(jīng)過此節(jié)點，不能再經(jīng)過了；如果不包括，就將其加入path容器3）直到搜索到str[length - 1]節(jié)點，說明成功找到，標(biāo)記result為true，標(biāo)記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.nowcoder.com/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.nowcoder.com/questionTerminal/c61c6999eecb4b8f88a98f66b273a3cc
來源：?？途W(wǎng)

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

鏈接：https://www.nowcoder.com/questionTerminal/c61c6999eecb4b8f88a98f66b273a3cc來源：?？途W(wǎng)public class Solution {    public boolean hasPath(char[] matrix, int rows, int cols, char[] str)    {        //標(biāo)志位，初始化為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(初始矩陣，索引行坐標(biāo)i，索引縱坐標(biāo)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;    }