每日算法之矩阵中的路径

JZ12 矩阵中的路径

描述

1. 请设计一个函数，用来判断在一个n乘m的矩阵中是否存在一条包含某长度为len的字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。

复制代码

思路

1. 我们看到他是从矩形中的一个点开始往他的上下左右四个方向查找，这个点可以是矩形中的任何一个点，所以代码的大致轮廓我们应该能写出来，就是遍历矩形所有的点，然后从这个点开始往他的4个方向走，因为是二维数组，所以有两个for循环，代码如下
2. public boolean hasPath (char[][] matrix, String word) {
3.     char[] words = word.toCharArray();
4.     for (int i = 0; i < matrix.length; i++) {
5.         for (int j = 0; j < matrix[0].length; j++) {
6.             //从[i,j]这个坐标开始查找
7.             if (dfs(matrix, words, i, j, 0))
8.                 return true;
9.         }
10.     }
11.     return false;
12. }
13. 这里关键代码是dfs这个函数，因为每一个点我们都可以往他的4个方向查找，所以我们可以把它想象为一棵4叉树，就是每个节点有4个子节点，而树的遍历我们最容易想到的就是递归，我们来大概看一下
15. boolean dfs(char[][] board, char[] word, int i, int j, int index) {
16.     if (边界条件的判断) {
17.         return;
18.     }
20.     一些逻辑处理
22.     boolean res;
23.     //往右
24.     res = dfs(board, word, i + 1, j, index + 1)
25.     //往左
26.     res |= dfs(board, word, i - 1, j, index + 1)
27.     //往下
28.     res |= dfs(board, word, i, j + 1, index + 1)
29.     //往上
30.     res |= dfs(board, word, i, j - 1, index + 1)
31.     //上面4个方向，只要有一个能查找到，就返回true；
32.     return res;
33. }

复制代码

代码

1. package mid.JZ12矩阵中的路径;
3. import java.util.*;
6. public class Solution {
7.     /**
8.      * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
9.      *
10.      *
11.      * @param matrix char字符型二维数组
12.      * @param word string字符串
13.      * @return bool布尔型
14.      */
15.     public boolean hasPath (char[][] matrix, String word) {
16.         // write code here
17.         char[] words = word.toCharArray();
18.         for (int i = 0; i < matrix.length; i++) {
19.             for (int j = 0; j < matrix[0].length; j++) {
20.                 if (dfs(matrix, words, i, j, 0)) {
21.                     return true;
22.                 }
23.             }
24.         }
25.         return false;
26.     }
28.     public boolean dfs(char[][] matrix,char[] word, int i, int j, int index) {
29.         //行
30.         int n = matrix.length;
31.         //列
32.         int m = matrix[0].length;
33.         if (i >= n || i < 0 || j >= m || j < 0 || matrix[i][j] != word[index]) {
34.             return false;
35.         }
36.         if (index == word.length - 1) return true;
38.         //记录当前坐标的值保存下来，防止重复使用
39.         char tmp = matrix[i][j];
40.         matrix[i][j] = '.';
42.         //走递归
43.         boolean res = (dfs(matrix, word, i + 1, j, index + 1) ||
44.                 dfs(matrix, word, i, j + 1, index + 1) ||
45.                 dfs(matrix, word, i - 1, j, index + 1) ||
46.                 dfs(matrix, word, i, j - 1, index + 1));
48.         //当前值复原
49.         matrix[i][j] = tmp;
50.         return res;
51.     }
52. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！