package algorithmBasic;
/**
* @author kegekeqi
* @version 1.0
* @date 2021-12-12 22:24
*/
public class HuiSuo {
public boolean hasPath(char[] matrix, int rows, int cols, char[] str) {
if (null == matrix || rows < 1 || cols < 1 || str == null) {
return false;
}
boolean[][] visited = new boolean[rows][cols];
for (int row = 0; row < rows; row++) {
for (int col = 0; col < cols; col++) {
if (hasPath(matrix, rows, cols, row, col, str, 0, visited)) {
return true;
}
}
}
return false;
}
private boolean hasPath(char[] matrix, int rows, int cols, int row, int col,
char[] str, int index, boolean[][] visited) {
if (index == str.length) {
return true;
}
if (row >= 0 && row < rows && col >= 0 && col < cols && !visited[row][col]
&& matrix[cols * row + col] == str[index]) {
visited[row][col] = true;
if (hasPath(matrix, rows, cols, row - 1, col, str, index + 1, visited)
|| hasPath(matrix, rows, cols, row + 1, col, str, index + 1, visited)
|| hasPath(matrix, rows, cols, row, col - 1, str, index + 1, visited)
|| hasPath(matrix, rows, cols, row, col + 1, str, index + 1, visited)) {
return true;
}
visited[row][col] = false;
}
return false;
}
}