JZ12 矩陣中的路徑
描述
請設計一個函式，用來判斷在一個n乘m的矩陣中是否存在一條包含某長度為len的字串所有字符的路徑，路徑可以從矩陣中的任意一個格子開始，每一步可以在矩陣中向左，向右，向上，向下移動一個格子，如果一條路徑經過了矩陣中的某一個格子，則該路徑不能再進入該格子，
思路
我們看到他是從矩形中的一個點開始往他的上下左右四個方向查找，這個點可以是矩形中的任何一個點，所以代碼的大致輪廓我們應該能寫出來，就是遍歷矩形所有的點，然后從這個點開始往他的4個方向走，因為是二維陣列，所以有兩個for回圈，代碼如下
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++) {
//從[i,j]這個坐標開始查找
if (dfs(matrix, words, i, j, 0))
return true;
}
}
return false;
}
這里關鍵代碼是dfs這個函式，因為每一個點我們都可以往他的4個方向查找，所以我們可以把它想象為一棵4叉樹，就是每個節點有4個子節點，而樹的遍歷我們最容易想到的就是遞回，我們來大概看一下
boolean dfs(char[][] board, char[] word, int i, int j, int index) {
if (邊界條件的判斷) {
return;
}
一些邏輯處理
boolean res;
//往右
res = dfs(board, word, i + 1, j, index + 1)
//往左
res |= dfs(board, word, i - 1, j, index + 1)
//往下
res |= dfs(board, word, i, j + 1, index + 1)
//往上
res |= dfs(board, word, i, j - 1, index + 1)
//上面4個方向，只要有一個能查找到，就回傳true；
return res;
}
代碼
package mid.JZ12矩陣中的路徑;
import java.util.*;
public class Solution {
/**
* 代碼中的類名、方法名、引數名已經指定，請勿修改，直接回傳方法規定的值即可
*
*
* @param matrix char字符型二維陣列
* @param word string字串
* @return bool布爾型
*/
public boolean hasPath (char[][] matrix, String word) {
// write code here
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;
}
public boolean dfs(char[][] matrix,char[] word, int i, int j, int index) {
//行
int n = matrix.length;
//列
int m = matrix[0].length;
if (i >= n || i < 0 || j >= m || j < 0 || matrix[i][j] != word[index]) {
return false;
}
if (index == word.length - 1) return true;
//記錄當前坐標的值保存下來，防止重復使用
char tmp = matrix[i][j];
matrix[i][j] = '.';
//走遞回
boolean res = (dfs(matrix, word, i + 1, j, index + 1) ||
dfs(matrix, word, i, j + 1, index + 1) ||
dfs(matrix, word, i - 1, j, index + 1) ||
dfs(matrix, word, i, j - 1, index + 1));
//當前值復原
matrix[i][j] = tmp;
return res;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/538599.html
標籤：其他
上一篇：重新認識下JVM級別的本地快取框架Guava Cache(3)——探尋實作細節與核心機制
下一篇：<八>理解抽象類