题解 | #矩阵中的路径#

矩阵中的路径

http://www.nowcoder.com/practice/2a49359695a544b8939c77358d29b7e6



public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param matrix char字符型二维数组 
     * @param word string字符串 
     * @return bool布尔型
     */
    public boolean hasPath (char[][] matrix, String word) {
        // write code here
        int n = matrix.length;
        int m = matrix[0].length;
        int length = word.length();
        for(int i = 0;i < n;i ++){
            for(int j = 0;j < m;j ++){
                if(matrix[i][j] == word.charAt(0)){
                    if(dfs(i,j,0,n,m,word,matrix)){
                        return true;
                    };
                }
            }
       }
        return false;
    }
    public boolean dfs(int i,int j,int index,int n,int m,String word,char[][] matrix){
        if(i >= n || i < 0 || j >= m || j < 0 || matrix[i][j] != word.charAt(index)){
            return false;
        }
        if(index == word.length()-1){
            return true;
        }
       char yuan = matrix[i][j];
       matrix[i][j] = '#';
       boolean isV = dfs(i+1,j,index+1,n,m,word,matrix) || 
                     dfs(i-1,j,index+1,n,m,word,matrix) ||
                     dfs(i,j+1,index+1,n,m,word,matrix) ||
                     dfs(i,j-1,index+1,n,m,word,matrix);
        matrix[i][j] = yuan;
        return isV;
    }
}
全部评论

相关推荐

点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务