剑指 Offer 12. 矩阵中的路径
- 题目类似于迷宫的搜索。
- 需要注意的是，需要首先判断起始搜索的位置，可能有多个起点，都需要一一尝试。
- 每轮迭代的时候记得将是否遍历标记数组还原为未遍历的状态。
package com.walegarrett.offer;
/**
* @Author WaleGarrett
* @Date 2020/12/9 9:09
*/
import java.util.Arrays;
/**
* [["a","b","c","e"],
* ["s","f","c","s"],
* ["a","d","e","e"]]
* 矩阵中不包含字符串“abfb”的路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入这个格子。
* 1 <= board.length <= 200
* 1 <= board[i].length <= 200
*/
public class Offer_12 {
private String word;
private boolean[][] travel;
private final int[][] direction = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
public boolean exist(char[][] board, String word) {
if(board == null)
return false;
if(word.length() == 0)
return true;
this.word = word;
travel = new boolean[board.length][board[0].length];
for(int i =0; i< board.length; i++){
for(int j =0; j< board[0].length; j++){
travel[i][j] = false;
}
}
for(int i =0; i< board.length; i++){
int len = board[0].length;
for(int j =0; j< len; j++){
if(board[i][j] != word.charAt(0))
continue;
travel[i][j] = true;
if(findPath(board, 0, i, j)){
return true;
}
travel[i][j] = false;
}
}
return false;
}
public boolean findPath(char[][] board, int pos, int x, int y){
if(pos >= word.length() - 1){
if(board[x][y] == word.charAt(pos))
return true;
return false;
}
//遍历四个方向
for(int i = 0; i< 4; i++){
int dx = x + direction[i][0];
int dy = y+ direction[i][1];
if(dx>=0 && dy>=0 && dx<board.length && dy< board[0].length && !travel[dx][dy]){
if(board[dx][dy] == word.charAt(pos + 1)){
travel[dx][dy] = true;
if(findPath(board, pos+1, dx, dy)){
travel[dx][dy] = false;
return true;
}else travel[dx][dy] = false;
}
}
}
return false;
}
}