矩阵中的路径（剑指offer 面试题66）

在矩阵中找到路径，很容易，递归就可以解决。

    public static boolean isPathInMatrix(String string, char[][] charMatrix){
        if(string==null||string.length()==0||charMatrix==null)
            return false;

        int H = charMatrix.length;
        int W = charMatrix[0].length;

        boolean[][] pathMatrix = new boolean[H][W];
        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) {
                pathMatrix[i][j] = false;
            }
        }

        for (int Y = 0; Y < H; Y++) {
            for (int X = 0; X < W; X++) {
                if(isPathInMatrix(string, 0, Y, X, charMatrix, pathMatrix)) {
                    System.out.println(Arrays.deepToString(pathMatrix));
                    return true;
                }
            }
        }

        System.out.println(Arrays.deepToString(pathMatrix));
        return false;
    }

    public static boolean isPathInMatrix(String string, int currentIndex, int Y, int X, char[][] charMatrix, boolean[][] pathMatrix) {
        if(currentIndex>=string.length()) {
            return true;
        }

        int H = charMatrix.length;
        int W = charMatrix[0].length;

        if((Y>=0&&Y<H&&X>=0&&X<W) && string.charAt(currentIndex)==charMatrix[Y][X]){
            pathMatrix[Y][X] = true;

            currentIndex += 1;
            if(currentIndex>=string.length()) {
                return true;
            }else{
                boolean ret = isPathInMatrix(string, currentIndex, Y-1, X, charMatrix, pathMatrix)
                        || isPathInMatrix(string, currentIndex, Y+1, X, charMatrix, pathMatrix)
                        || isPathInMatrix(string, currentIndex, Y, X-1, charMatrix, pathMatrix)
                        || isPathInMatrix(string, currentIndex, Y, X+1, charMatrix, pathMatrix);

                if(!ret) {
                    pathMatrix[Y][X] = false;
                }
                return ret;
            }
        }else{
            return false;
        }
    }

测试代码：

//        String string = "bcced";
        String string = "abcb";
        char[][] charMatrix = new char[][]{
                {'a','b','c','e'},
                {'s','f','c','s'},
                {'a','d','e','e'},
        };
        boolean ret = isPathInMatrix(string, charMatrix);
        System.out.println(ret);