矩阵中的路径

矩阵中的路径

http://www.nowcoder.com/questionTerminal/c61c6999eecb4b8f88a98f66b273a3cc

题目描述:
请设计一个函数,用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始,每一步可以在矩阵中向左,向右,向上,向下移动一个格子。如果一条路径经过了矩阵中的某一个格子,则该路径不能再进入该格子。
思路
使用递归和回溯的思想,回溯思想:设置一个标记矩阵,矩阵与原本矩阵相同,true表示走过了,false表示没走过,当这条路径不匹配的时候,再把原来标记位true的标记位false;

public class Solution {

    public static boolean hasPath(char[] matrix, int rows, int cols, char[] str)
    {
        //把一维数组转换成二维的
        char[][] board = new char[rows][cols];
        int ceng = 0 ;
        int x =0 ;
        for(int i =0 ;i<matrix.length ;i++){
            if(x == cols) {
                x= 0;
                ceng++;
            }
            board[ceng][x] = matrix[i];
            x++;
        }
        for(int i =0 ;i<rows ;i++){
            for(int j = 0;j<cols;j++){
                System.out.print(board[i][j]);
            }
            System.out.println();
        }

        //
        boolean vis[][] = new boolean[rows][cols];
        int index = 0;
        //
        for(int i =0 ;i<rows ;i++){
            for(int j = 0;j<cols;j++){
                if(solve(board,str,i,j,vis,index) == true) {
                    return true;
                }
            }
        }
        return false;


    }

    private static boolean solve(char[][] board, char[] str, int i, int j, boolean[][] vis,int index) {

        //处理越界
        if(i< 0|| i>board.length-1 || j<0 ||j>board[0].length-1 || vis[i][j]) {
            return false;
        }
        //匹配到不满足的情况
        if(str[index] !=  board[i][j]) {
            return false;
        }
        //匹配成功
        if(index == str.length-1) {
            return true;
        }

        vis[i][j] = true;
        boolean flag = solve(board,str,i+1,j,vis,index+1)|| //向下
                       solve(board,str,i-1,j,vis,index+1)|| //向上 
                       solve(board,str,i,j+1,vis,index+1)|| //向右
                       solve(board,str,i,j-1,vis,index+1);  //向左
        vis[i][j] = false;

        return flag;
    }


}
全部评论

相关推荐

11-21 13:04
已编辑
门头沟学院 算法工程师
点赞 评论 收藏
分享
11-18 13:45
已编辑
门头沟学院 Java
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务