12. 矩阵中的路径(剑指 Offer 题解Java版)

五角钱的程序员 2020-03-27

217

文章目录

12. 矩阵中的路径

题目描述
题目链接
解题思路
实现代码

12. 矩阵中的路径

题目描述

判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向上下左右移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。

例如下面的矩阵包含了一条 bfce 路径。

题目链接

牛客网

https://www.nowcoder.com/practice/c61c6999eecb4b8f88a98f66b273a3cc?tpId=13&tqId=11218&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking&from=cyc_github

解题思路

使用回溯法（backtracking）进行求解，它是一种暴力搜索方法，通过搜索所有可能的结果来求解问题。回溯法在一次搜索结束时需要进行回溯（回退），将这一次搜索过程中设置的状态进行清除，从而开始一次新的搜索过程。例如下图示例中，从 f 开始，下一步有 4 种搜索可能，如果先搜索 b，需要将 b 标记为已经使用，防止重复使用。在这一次搜索结束之后，需要将 b 的已经使用状态清除，并搜索 c。

本题的输入是数组而不是矩阵（二维数组），因此需要先将数组转换成矩阵。

实现代码


package 矩阵中的路径;/*
作者     :XiangLin
创建时间 :09/03/2020 22:59
文件     :StringPathInMatrix.java
IDE      :IntelliJ IDEA
*/

// 题目：请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有
// 字符的路径。路径可以从矩阵中任意一格开始，每一步可以在矩阵中向左、右、
// 上、下移动一格。如果一条路径经过了矩阵的某一格，那么该路径不能再次进入
// 该格子。例如在下面的3×4的矩阵中包含一条字符串“bfce”的路径（路径中的字
// 母用下划线标出）。但矩阵中不包含字符串“abfb”的路径，因为字符串的第一个
// 字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入这个格子。
// A B T G
// C F C S
// J D E H

public class StringPathInMatrix {
    private final static int[][] next = {{0,-1},{0,1},{-1,0},{1,0}};
    private int rows;
    private int cols;

    public boolean hasPath(char[] array,int rows,int cols,char[] str){
        if (rows == 0 || cols == 0)
            return  false;

        this.rows = rows;
        this.cols = cols;
        boolean[][] marked = new boolean[rows][cols];
        char[][] matrix = buildMatrix(array);

        for(int i = 0; i < rows; i++){
            for (int j = 0; j< cols; j++){
                if (backtracking(matrix,str,marked,0,i,j))
                    return true;
            }
        }
        return true;

    }
    private boolean backtracking(char[][] matrix,char[] str,boolean[][] marked,int pathLen,int r,int c){
        if (pathLen == str.length) return true;
        if (r < 0 || r >= rows || c < 0 || c >= cols || matrix[r][c] != str[pathLen] || marked[r][c]) return false;

        marked[r][c] = true;
//        for(元素类型t 元素变量x : 遍历对象obj){
//             引用了x的java语句;
//             }
        for (int[] n :next){
            if (backtracking(matrix,str,marked,pathLen+1,r+n[0],c+n[1]))
                return true;
        }
        marked[r][c] = false;
        return false;
    }


    private char[][] buildMatrix(char[] array){
        char[][] matrix = new char[rows][cols];
        for (int r = 0, idx = 0; r < rows; r++){
            for (int c = 0; c < cols; c++){
                matrix[r][c] = array[idx++];
            }
        }
        return matrix;
    }

    public static void main(String[] args) {
        StringPathInMatrix p = new StringPathInMatrix();

        char[] s = {'A','B','T','G','C','F','C','S','J','D','E','H'};
        char[] t = {'A','H','G','S','E'};

        boolean c = p.hasPath(s,3,4,t);
        System.out.println(c);

    }
}