矩陣中的路徑

題目

請設計一個函數，用來判斷在一個n乘m的矩陣中是否存在一條包含某長度為len的字符串所有字符的路徑。路徑可以從矩陣中的任意一個格子開始，每一步可以在矩陣中向左，向右，向上，向下移動一個格子。如果一條路徑經過了矩陣中的某一個格子，則該路徑不能再進入該格子。 例如：
[a b c e]
[s f c s]
[a d e e]
矩陣中包含一條字符串"bcced"的路徑，但是矩陣中不包含"abcb"路徑，因為字符串的第一個字符b占據了矩陣中的第一行第二個格子之后，路徑不能再次進入該格子。

思路

采用回溯法思想，對于矩陣中各個坐標一個個嘗試，并遞歸查找對應位置上下左右位置，直到查找完畢；
牛客鏈接以及題解

代碼實現

   public boolean hasPath (char[][] matrix, String word) {char[] words = word.toCharArray();//遍歷查找矩陣各個位置是否滿足for(int i = 0 ; i < matrix.length ; i++){for(int j = 0; j < matrix[0].length;j++){if(dfs(matrix,words,i,j,0)){return true;}}}return false;}/*** matrix 表示二維查找矩陣* 目標字符串* i 表示 行號* j 表示 列號* index 表示字符當前下標*/private boolean dfs(char[][] matrix,char[] words,int i,int j,int index){//邊界判斷if(i < 0 || i >= matrix.length || j < 0 || j >= matrix[0].length || words[index] != matrix[i][j]){return false;}//匹配結束，直接返回trueif(index == words.length -1){return true;}//記錄下當前字符，用于后續還原char temp = matrix[i][j];//使用過的字符設置為特殊符號，標記為已使用，后續無法再次匹配成功matrix[i][j] = '@';//遞歸查找上下左右字符是否匹配成功boolean res = dfs(matrix,words,i-1,j,index+1) || dfs(matrix,words,i+1,j,index+1) ||dfs(matrix,words,i,j-1,index+1) || dfs(matrix,words,i,j+1,index+1);//還原字符，用于再次匹配matrix[i][j] = temp;return res;}

機器人的運動范圍

題目

地上有一個 rows 行和 cols 列的方格。坐標從 [0,0] 到 [rows-1,cols-1] 。一個機器人從坐標 [0,0] 的格子開始移動，每一次只能向左，右，上，下四個方向移動一格，但是不能進入行坐標和列坐標的數位之和大于 threshold 的格子。 例如，當 threshold 為 18 時，機器人能夠進入方格 [35,37] ，因為 3+5+3+7 = 18。但是，它不能進入方格 [35,38] ，因為 3+5+3+8 = 19 。請問該機器人能夠達到多少個格子？
牛客鏈接

思路

同樣是采用回溯法進行解題，我們只需要正確的處理邊界判斷邏輯，然后套用通用模板即可；

代碼實現

 public int movingCount(int threshold, int rows, int cols) {//用于記錄當前下標是否被訪問過boolean[][] isVisited = new boolean[rows][cols];//從 0,0下標開始訪問return dfs(threshold,isVisited,rows,cols,0,0);}private int dfs(int threshold,boolean[][] isVisited,int rows,int cols, int i,int j){//處理訪問邊界if(i<0 || i>=rows || j<0 || j>=cols){return 0;}//訪問過的 或者不滿足threshold閾值的過濾掉if(isVisited[i][j] || sum(i,j) > threshold){return 0;}  //標記已訪問過isVisited[i][j] = true;//上下左右運動return 1+ dfs(threshold,isVisited,rows,cols,i-1,j) + dfs(threshold,isVisited,rows,cols,i+1,j) +  dfs(threshold,isVisited,rows,cols,i,j-1) + dfs(threshold,isVisited,rows,cols,i,j+1);}