【剑指Offer 12】矩阵中的路径
/*** 剑指 Offer 12. 矩阵中的路径
* https://leetcode.cn/problems/ju-zhen-zhong-de-lu-jing-lcof/
*
* 思路：深度优先搜索
* */
public class Solution {
private char[][] board;
private String word;
private int m;
private int n;
private boolean[][] marked;
public boolean exist(char[][] board, String word) {
this.board = board;
this.word = word;
m = board.length;
n = board.length;
marked = new boolean;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (board != word.charAt(0)) {
continue;
}
if(dfs(i, j, 0)) {
return true;
}
}
}
return false;
}
private boolean dfs(int i, int j, int index) {
if (index == word.length()) {
return true;
}
if (i < 0 || i >= m || j < 0 || j >= n) {
return false;
}
if (marked == true || board != word.charAt(index)) {
return false;
}
marked = true;
index++;
boolean result = dfs(i + 1, j, index)
|| dfs(i - 1, j, index)
|| dfs(i, j + 1, index)
|| dfs(i, j - 1, index);
marked = false;
return result;
}
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]