[剑指Offer]-矩阵中的路径

题目描述

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。 例如在下面的3x4的矩阵中包含一条字符串"bcced"的路径（路径中的字母用斜体表示）。但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入这个格子。

我就觉得这递归思想就是一个反人类的思想！

回溯法找路径，可以看作下面的一个树结构，在每个满足条件的节点，寻找到相邻的节点，然后在相邻节点里面找个满足第i步的元素，如果找不到就回退一步。

解题思路

• 遍历矩阵找到一个入口。
• 定义一个数组用于储存当前节点是否遍历过的信息。
• 寻找相邻节点是否有满足条件的节点。
  • 下面代码中，当矩阵坐标为（row，col）的格子和路径字符串中下标为pathLength的字符一样时，从4个相邻的格子（row，col-1）、（row-1，col）、（row，col+1）以及（row+1，col）中去定位路径字符串中下标为pathLength+1的字符。
  • 如果4个相邻的格子都没有匹配字符串中下标为pathLength+1的字符，表明当前路径字符串中下标为pathLength的字符在矩阵中的定位不正确，我们需要回到前一个字符串（pathLength-1），然后重新定位。

一直重复这个过程，直到路径字符串上所有字符都在矩阵中找到格式的位置（此时pathLength>startch.length-1 ）。

算法图解

• 注意代码中对于结束递归的条件的设定！
• 是否访问数组的赋值！

参考代码：

package offer;

import java.util.Arrays;

public class Offer12 {
    public static void main(String[] args) {
        char nums[][] = {{'a', 'b', 't', 'g'}, {'c', 'f', 'c', 's'}, {'j', 'd', 'e', 'h'}};
        int rows = nums.length;
        int cols = nums[0].length;
        char startch[] = {'b', 'f', 'c', 'h'};
        boolean tag = hashPath(nums, rows, cols, startch);
        if (tag) {
            System.out.println("存在路径");
        } else {
            System.out.println("不存在路径");
        }

    }

    static boolean hashPath(char nums[][], int rows, int cols, char startch[]) {

        if (nums == null || rows <= 1 || cols <= 1 || startch == null) {
            return false;
        }
        boolean visited[] = new boolean[rows * cols];
        Arrays.fill(visited, false);
        int pathLength = 0;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (hashPathCore(nums, i, j, rows, cols, startch, pathLength, visited)) {
                    return true;
                }
            }
        }
        return false;
    }

    private static boolean hashPathCore(char[][] nums, int row, int col, int rows, int cols, char[] startch, int pathLength, boolean[] visited) {
        if (pathLength>startch.length-1 ) {
            return true;
        }
        boolean hasPath = false;
        if (row < rows && col < cols && col >= 0 && row >= 0 && nums[row][col] == startch[pathLength] && !visited[row * cols + col]) {
            ++pathLength;
            visited[row * cols + col] = true;
            hasPath = hashPathCore(nums, row - 1, col, rows, cols, startch, pathLength, visited)
                    || hashPathCore(nums, row + 1, col, rows, cols, startch, pathLength, visited)
                    || hashPathCore(nums, row, col - 1, rows, cols, startch, pathLength, visited)
                    || hashPathCore(nums, row, col + 1, rows, cols, startch, pathLength, visited);
            if (!hasPath) {
                --pathLength;
                visited[row * cols + col] = false;
            }
        }
        return hasPath;
    }
}

---

附录

该题源码在我的 ????Github 上面！