矩阵中的路径
题目描述
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。例如，在下面的3×4的矩阵中包含一条字符串“bfce”的路径（路径中的字母用加粗标出）。
[["a","b","c","e"],
["s","f","c","s"],
["a","d","e","e"]]
但矩阵中不包含字符串“abfb”的路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入这个格子。
示例：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true
输入：board = [["a","b"],["c","d"]], word = "abcd"
输出：false
提示：
1 <= board.length <= 200
1 <= board[i].length <= 200
题目分析
开门见山：回溯法
初始条件：当前在board里的坐标 x = 0, y = 0,
当前对比到的字符串下标index = 0
访问记录着visited（和board同形）全为false
- 1.如果index = word.size 证明已经找到路径，return true
- 2.如果visited[ x ][ y ]为true，证明这个点已经在路径里，不能重复访问，return false
- 3.如果x y越界或者比0小，return false
- 4.如果board[ x ] [ y ] != word[ index ] 直接return false， 因为这条路行不通，往下一条路走
- 5.如果board[ x ] [ y ] == word[ index ]，那么就标记visited[ x ][ y ]为true，即已经访问了这个点，然后向它的四个方向继续探索，此时x y根据方向进行变化，index + 1，回到第一步
- 6.接第五步，如果这个点的四个方向都走不通，证明这条路是不同的，就回溯，需要将visited[ x ][ y ]重新设置回false
下面我画一个图方便大家理解这个过程，大家也可以结合图来一步一步的理解上面的流程（橙色代表不匹配，需要回溯，四个方向顺序是上右左下）：
boolean[][] visited;
int[][] direction = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
String word;
char[][] board;
public boolean exist(char[][] board, String word) {
this.word = word;
this.board = board;
visited = new boolean[board.length][board[0].length];
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[i].length; j++) {
if (solution(i, j, 0))
return true;
}
}
return false;
}
public boolean solution( int x, int y, int index) {
if (index == word.length())
return true;
if (x < 0 || y < 0 || x > board.length - 1 || y > board[0].length - 1)
return false;
if (visited[x][y] || board[x][y] != word.charAt(index))
return false;
visited[x][y] = true;
for (int i = 0; i < 4; i++) {
if (solution( x + direction[i][0], y + direction[i][1], index + 1))
return true;
}
visited[x][y] = false;
return false;
}
