面试题12: 矩阵中的路径(动态规划1)

package cn.zxy.interview;

import java.util.Arrays;
import java.util.HashMap;

/**
 * 回溯法:
 * 到达一个节点后, 首先判断该节点是否满足条件, 如果不满足, 递归返回;
 * 如果满足, 更新相应的访问记录及目标, 然后向下试探节点
 * 如果所有向下的节点不满足, 则该节点无效, 取消记录, 向上回溯
 */

public class A12_TwoDimensionPath {
    public static boolean hasPath(int[][] a, int rows, int columns, String str){
        int[][] visited = new int[100][100];


        int pathLength = 0;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                if(hasPathCore(a, i, j, str, pathLength, visited)){
                    return true;
                }
            }
        }
        return false;
    }

    private static boolean hasPathCore(int[][] a, int row, int column, String str, int pathLength, int[][] visited) {
        // 当匹配长度等于字符长度时, 匹配成功
        if (pathLength == str.length()) return true;

        boolean hasPath = false;
        // 判断该节点是否满足匹配目标
        if(row >= 0 && row < a.length && column >= 0 && column < a[0].length
                && a[row][column] == str.charAt(pathLength)
                && visited[row][column] != 1){

            System.out.println((char)a[row][column]);
            pathLength++;
            visited[row][column] = 1;


            // 向下判断
            hasPath = hasPathCore(a, row, column-1, str, pathLength, visited)
                   || hasPathCore(a, row-1, column, str, pathLength, visited)
                   || hasPathCore(a, row, column+1, str, pathLength, visited)
                   || hasPathCore(a, row+1, column, str, pathLength, visited);
            // 递归返回
            if(hasPath){
                System.out.println("(" + row + ", " + column + ") -- " + (char)a[row][column]);
            }else{
                pathLength--;
                visited[row][column] = 0;
            }
        }
        return hasPath;
    }


    public static void main(String[] args) {

        int[][] a = {{'a', 'b', 't', 'g'},
                     {'c', 'f', 'c', 's'},
                     {'j', 'd', 'e', 'h'}};

        boolean hasPath = hasPath(a, 3, 4, "bfce");

    }
}