第 12 题：矩阵中的路径
传送门：AcWing：矩阵中的路径。
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。
路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。
如果一条路径经过了矩阵中的某一个格子，则之后不能再次进入这个格子。
注意：
- 输入的路径不为空；
- 所有出现的字符均为大写英文字母；
样例：
matrix= [ ["A","B","C","E"], ["S","F","C","S"], ["A","D","E","E"] ] str="BCCE" , return "true" str="ASAE" , return "false"
思路：典型的 floodfill 解法，本质上是递归回溯算法。
Python 代码：
class Solution(object):
directions = [(-1, 0), (1, 0), (0, 1), (0, -1)]
def hasPath(self, matrix, string):
"""
:type matrix: List[List[str]]
:type string: str
:rtype: bool
"""
rows = len(matrix)
if rows == 0:
return False
cols = len(matrix[0])
marked = [[False for _ in range(cols)] for _ in range(rows)]
for i in range(rows):
for j in range(cols):
if self.__has_path(matrix, string, 0, i, j, marked, rows, cols):
return True
return False
def __has_path(self, matrix, word, index, start_x, start_y, marked, m, n):
# 注意：首先判断极端情况
if index == len(word) - 1:
return matrix[start_x][start_y] == word[-1]
if matrix[start_x][start_y] == word[index]:
# 先占住这个位置，搜索不成功的话，要释放掉
marked[start_x][start_y] = True
for direction in self.directions:
new_x = start_x + direction[0]
new_y = start_y + direction[1]
if 0 <= new_x < m and 0 <= new_y < n and not marked[new_x][new_y]:
if self.__has_path(matrix, word, index + 1, new_x, new_y, marked, m, n):
return True
marked[start_x][start_y] = False
return False
if __name__ == '__main__':
matrix = [
["A", "B", "C", "E"],
["S", "F", "E", "S"],
["A", "D", "E", "E"]
]
str = "ABCEFSADEESE"
solution = Solution()
result = solution.hasPath(matrix, str)
print(result)
同 LeetCode 第 79 题，传送门：79. 单词搜索，牛客网 online judge 地址。
给定一个二维网格和一个单词，找出该单词是否存在于网格中。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例:
board = [ ['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E'] ]给定 word = "ABCCED", 返回 true.
给定 word = "SEE", 返回 true.
给定 word = "ABCB", 返回 false.
思路：其实就是 floodfill 算法，这是一个非常基础的算法，一定要掌握。特别要弄清楚，marked 数组的作用，一开始要占住这个位置，发现此路不通的时候，要释放掉。
Python 代码：
class Solution:
# (x-1,y)
# (x,y-1) (x,y) (x,y+1)
# (x+1,y)
directions = [(0, -1), (-1, 0), (0, 1), (1, 0)]
def exist(self, board, word):
"""
:type board: List[List[str]]
:type word: str
:rtype: bool
"""
m = len(board)
n = len(board[0])
marked = [[False for _ in range(n)] for _ in range(m)]
for i in range(m):
for j in range(n):
# 对每一个格子都从头开始搜索
if self.__search_word(board, word, 0, i, j, marked, m, n):
return True
return False
def __search_word(self, board, word, index, start_x, start_y, marked, m, n):
# 先写递归终止条件
if index == len(word) - 1:
return board[start_x][start_y] == word[index]
# 中间匹配了，再继续搜索
if board[start_x][start_y] == word[index]:
# 先占住这个位置，搜索不成功的话，要释放掉
marked[start_x][start_y] = True
for direction in self.directions:
new_x = start_x + direction[0]
new_y = start_y + direction[1]
if 0 <= new_x < m and 0 <= new_y < n and \
not marked[new_x][new_y] and \
self.__search_word(board, word,
index + 1,
new_x, new_y,
marked, m, n):
return True
marked[start_x][start_y] = False
return False
Java 代码：
public class Solution {
/**
* x-1,y
* x,y-1 x,y x,y+1
* x+1,y
*/
private int[][] direct = new int[][]{{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
public boolean hasPath(char[] matrix, int rows, int cols, char[] str) {
int len = matrix.length;
if (len == 0) {
return false;
}
boolean[] marked = new boolean[len];
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (dfs(matrix, rows, cols, str, str.length, marked, i, j, 0)) {
return true;
}
}
}
return false;
}
private boolean dfs(char[] matrix, int rows, int cols, char[] str, int len, boolean[] marked, int i, int j, int start) {
// 匹配到最后，说明找到一条路径
int index = getIndex(i, j, cols);
if (start == len - 1) {
return matrix[index] == str[start];
}
// 要特别小心！
marked[index] = true;
if (matrix[index] == str[start]) {
// 当前匹配了，才开始尝试走后面的路
for (int k = 0; k < 4; k++) {
// 特别小心，一定是一个初始化的新的变量
int newi = i + direct[k][0];
int newj = j + direct[k][1];
int nextIndex = getIndex(newi, newj, cols);
if (inArea(newi, newj, rows, cols) && !marked[nextIndex]) {
// marked[nextIndex] = true; 不在这里设置
if (dfs(matrix, rows, cols, str, len, marked, newi, newj, start + 1)) {
return true;
}
// marked[nextIndex] = false; 不在这里设置
}
}
}
// 要特别小心！
marked[index] = false;
return false;
}
private int getIndex(int x, int y, int cols) {
return x * cols + y;
}
private boolean inArea(int x, int y, int rows, int cols) {
return x >= 0 && x < rows && y >= 0 && y < cols;
}
public static void main(String[] args) {
char[] matrix = new char[]{'a', 'b', 't', 'g',
'c', 'f', 'c', 's',
'j', 'd', 'e', 'h'};
int rows = 3;
int cols = 4;
Solution solution = new Solution();
char[] str = "hscfdeh".toCharArray();
boolean hasPath = solution.hasPath(matrix, rows, cols, str);
System.out.println(hasPath);
}
}
Java 代码：
public class Solution {
/**
* x-1,y
* x,y-1 x,y x,y+1
* x+1,y
*/
private int[][] direct = new int[][]{{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
public boolean hasPath(char[] matrix, int rows, int cols, char[] str) {
int len = matrix.length;
if (len == 0) {
return false;
}
boolean[] marked = new boolean[len];
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (dfs(matrix, rows, cols, str, str.length, marked, i, j, 0)) {
return true;
}
}
}
return false;
}
private boolean dfs(char[] matrix, int rows, int cols, char[] str, int len, boolean[] marked, int i, int j, int start) {
// 匹配到最后，说明找到一条路径
int index = getIndex(i, j, cols);
if (start == len - 1) {
return matrix[index] == str[start];
}
// 要特别小心！
marked[index] = true;
if (matrix[index] == str[start]) {
// 当前匹配了，才开始尝试走后面的路
for (int k = 0; k < 4; k++) {
// 特别小心，一定是一个初始化的新的变量
int newi = i + direct[k][0];
int newj = j + direct[k][1];
int nextIndex = getIndex(newi, newj, cols);
if (inArea(newi, newj, rows, cols) && !marked[nextIndex]) {
// marked[nextIndex] = true; 不在这里设置
if (dfs(matrix, rows, cols, str, len, marked, newi, newj, start + 1)) {
return true;
}
// marked[nextIndex] = false; 不在这里设置
}
}
}
// 要特别小心！
marked[index] = false;
return false;
}
private int getIndex(int x, int y, int cols) {
return x * cols + y;
}
private boolean inArea(int x, int y, int rows, int cols) {
return x >= 0 && x < rows && y >= 0 && y < cols;
}
public static void main(String[] args) {
char[] matrix = new char[]{'a', 'b', 't', 'g',
'c', 'f', 'c', 's',
'j', 'd', 'e', 'h'};
int rows = 3;
int cols = 4;
Solution solution = new Solution();
char[] str = "hscfdeh".toCharArray();
boolean hasPath = solution.hasPath(matrix, rows, cols, str);
System.out.println(hasPath);
}
}
